{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Handling Sum Queries After Update"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #segment-tree #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #线段树 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: handleQuery"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #更新数组后处理求和查询"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个下标从 <strong>0</strong>&nbsp;开始的数组&nbsp;<code>nums1</code> 和&nbsp;<code>nums2</code>&nbsp;，和一个二维数组&nbsp;<code>queries</code>&nbsp;表示一些操作。总共有 3 种类型的操作：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>操作类型 1 为&nbsp;<code>queries[i]&nbsp;= [1, l, r]</code>&nbsp;。你需要将 <code>nums1</code>&nbsp;从下标&nbsp;<code>l</code>&nbsp;到下标 <code>r</code>&nbsp;的所有 <code>0</code>&nbsp;反转成 <code>1</code> 并且所有&nbsp;<code>1</code>&nbsp;反转成 <code>0</code>&nbsp;。<code>l</code>&nbsp;和 <code>r</code>&nbsp;下标都从 <strong>0</strong>&nbsp;开始。</li>\n",
    "\t<li>操作类型 2 为&nbsp;<code>queries[i]&nbsp;= [2, p, 0]</code>&nbsp;。对于&nbsp;<code>0 &lt;= i &lt; n</code>&nbsp;中的所有下标，令&nbsp;<code>nums2[i] =&nbsp;nums2[i]&nbsp;+ nums1[i]&nbsp;* p</code>&nbsp;。</li>\n",
    "\t<li>操作类型 3 为&nbsp;<code>queries[i]&nbsp;= [3, 0, 0]</code>&nbsp;。求&nbsp;<code>nums2</code>&nbsp;中所有元素的和。</li>\n",
    "</ol>\n",
    "\n",
    "<p>请你返回一个&nbsp;<em>数组</em>，包含&nbsp;<em>所有第三种操作类型&nbsp;</em>的答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums1 = [1,0,1], nums2 = [0,0,0], queries = [[1,1,1],[2,1,0],[3,0,0]]\n",
    "<b>输出：</b>[3]\n",
    "<strong>解释：</strong>第一个操作后 nums1 变为 [1,1,1] 。第二个操作后，nums2 变成 [1,1,1] ，所以第三个操作的答案为 3 。所以返回 [3] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums1 = [1], nums2 = [5], queries = [[2,0,0],[3,0,0]]\n",
    "<b>输出：</b>[5]\n",
    "<b>解释：</b>第一个操作后，nums2 保持不变为 [5] ，所以第二个操作的答案是 5 。所以返回 [5] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums1.length,nums2.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums1.length = nums2.length</code></li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>queries[i].length = 3</code></li>\n",
    "\t<li><code>0 &lt;= l &lt;= r &lt;= nums1.length - 1</code></li>\n",
    "\t<li><code>0 &lt;= p &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums1[i] &lt;= 1</code></li>\n",
    "\t<li><code>0 &lt;= nums2[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [handling-sum-queries-after-update](https://leetcode.cn/problems/handling-sum-queries-after-update/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [handling-sum-queries-after-update](https://leetcode.cn/problems/handling-sum-queries-after-update/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,1]\\n[0,0,0]\\n[[1,1,1],[2,1,0],[3,0,0]]', '[1]\\n[5]\\n[[2,0,0],[3,0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "  def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "    n1, cur, ans = 0, sum(nums2), []\n",
    "    for i in range(len(nums1) - 1, -1, -1):\n",
    "      n1 = (n1 << 1) | nums1[i]\n",
    "    for x, l, r in queries:\n",
    "      if x == 1:\n",
    "        n1 ^= (1 << (r - l + 1)) - 1 << l\n",
    "      elif x == 2:\n",
    "        cur += n1.bit_count() * l\n",
    "      else:\n",
    "        ans.append(cur)\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ans, x, s = [], 0, sum(nums2)\n",
    "        for i in reversed(nums1): x = (x << 1) | i\n",
    "        for qx in queries:\n",
    "            if qx[0] == 1: x ^= (mask := ((1 << (qx[2] - qx[1] + 1)) - 1) << qx[1])\n",
    "            if qx[0] == 2: s = s+ x.bit_count()*qx[1]\n",
    "            if qx[0] == 3: ans.append(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n1, val, ret = 0, sum(nums2), []\n",
    "        for i in reversed(nums1): n1 = (n1 << 1) | i\n",
    "        for t, l, r in queries:\n",
    "            if t == 1: n1 ^= ((1 << (r + 1 - l)) - 1) << l\n",
    "            elif t == 2: val += n1.bit_count() * l\n",
    "            else: ret.append(val)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n1, val, ret = 0, sum(nums2), []\n",
    "        for i in reversed(nums1): n1 = (n1 << 1) | i\n",
    "        for t, l, r in queries:\n",
    "            if t == 1: n1 ^= ((1 << (r + 1 - l)) - 1) << l\n",
    "            elif t == 2: val += n1.bit_count() * l\n",
    "            else: ret.append(val)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ans, x, s = [], int(''.join(map(str, nums1[::-1])), 2), sum(nums2)\n",
    "        for qx in queries:\n",
    "            if qx[0] == 1: x ^= (mask := ((1 << (qx[2] - qx[1] + 1)) - 1) << qx[1])\n",
    "            if qx[0] == 2: s = s+ x.bit_count()*qx[1]\n",
    "            if qx[0] == 3: ans.append(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import typing\n",
    "\n",
    "def _ceil_pow2(n: int) -> int:\n",
    "    x = 0\n",
    "    while (1 << x) < n:\n",
    "        x += 1\n",
    "\n",
    "    return x\n",
    "\n",
    "def _bsf(n: int) -> int:\n",
    "    x = 0\n",
    "    while n % 2 == 0:\n",
    "        x += 1\n",
    "        n //= 2\n",
    "\n",
    "    return \n",
    "\n",
    "\n",
    "class LazySegTree:\n",
    "    def __init__(\n",
    "            self,\n",
    "            op: typing.Callable[[typing.Any, typing.Any], typing.Any],\n",
    "            e: typing.Any,\n",
    "            mapping: typing.Callable[[typing.Any, typing.Any], typing.Any],\n",
    "            composition: typing.Callable[[typing.Any, typing.Any], typing.Any],\n",
    "            id_: typing.Any,\n",
    "            v: typing.Union[int, typing.List[typing.Any]]) -> None:\n",
    "        self._op = op\n",
    "        self._e = e\n",
    "        self._mapping = mapping\n",
    "        self._composition = composition\n",
    "        self._id = id_\n",
    "\n",
    "        if isinstance(v, int):\n",
    "            v = [e] * v\n",
    "\n",
    "        self._n = len(v)\n",
    "        self._log = _ceil_pow2(self._n)\n",
    "        self._size = 1 << self._log\n",
    "        self._d = [e] * (2 * self._size)\n",
    "        self._lz = [self._id] * self._size\n",
    "        for i in range(self._n):\n",
    "            self._d[self._size + i] = v[i]\n",
    "        for i in range(self._size - 1, 0, -1):\n",
    "            self._update(i)\n",
    "\n",
    "    def set(self, p: int, x: typing.Any) -> None:\n",
    "        assert 0 <= p < self._n\n",
    "\n",
    "        p += self._size\n",
    "        for i in range(self._log, 0, -1):\n",
    "            self._push(p >> i)\n",
    "        self._d[p] = x\n",
    "        for i in range(1, self._log + 1):\n",
    "            self._update(p >> i)\n",
    "\n",
    "    def get(self, p: int) -> typing.Any:\n",
    "        assert 0 <= p < self._n\n",
    "\n",
    "        p += self._size\n",
    "        for i in range(self._log, 0, -1):\n",
    "            self._push(p >> i)\n",
    "        return self._d[p]\n",
    "\n",
    "    def prod(self, left: int, right: int) -> typing.Any:\n",
    "        assert 0 <= left <= right <= self._n\n",
    "\n",
    "        if left == right:\n",
    "            return self._e\n",
    "\n",
    "        left += self._size\n",
    "        right += self._size\n",
    "\n",
    "        for i in range(self._log, 0, -1):\n",
    "            if ((left >> i) << i) != left:\n",
    "                self._push(left >> i)\n",
    "            if ((right >> i) << i) != right:\n",
    "                self._push(right >> i)\n",
    "\n",
    "        sml = self._e\n",
    "        smr = self._e\n",
    "        while left < right:\n",
    "            if left & 1:\n",
    "                sml = self._op(sml, self._d[left])\n",
    "                left += 1\n",
    "            if right & 1:\n",
    "                right -= 1\n",
    "                smr = self._op(self._d[right], smr)\n",
    "            left >>= 1\n",
    "            right >>= 1\n",
    "\n",
    "        return self._op(sml, smr)\n",
    "\n",
    "    def all_prod(self) -> typing.Any:\n",
    "        return self._d[1]\n",
    "\n",
    "    def apply(self, left: int, right: typing.Optional[int] = None,\n",
    "              f: typing.Optional[typing.Any] = None) -> None:\n",
    "        assert f is not None\n",
    "\n",
    "        if right is None:\n",
    "            p = left\n",
    "            assert 0 <= left < self._n\n",
    "\n",
    "            p += self._size\n",
    "            for i in range(self._log, 0, -1):\n",
    "                self._push(p >> i)\n",
    "            self._d[p] = self._mapping(f, self._d[p])\n",
    "            for i in range(1, self._log + 1):\n",
    "                self._update(p >> i)\n",
    "        else:\n",
    "            assert 0 <= left <= right <= self._n\n",
    "            if left == right:\n",
    "                return\n",
    "\n",
    "            left += self._size\n",
    "            right += self._size\n",
    "\n",
    "            for i in range(self._log, 0, -1):\n",
    "                if ((left >> i) << i) != left:\n",
    "                    self._push(left >> i)\n",
    "                if ((right >> i) << i) != right:\n",
    "                    self._push((right - 1) >> i)\n",
    "\n",
    "            l2 = left\n",
    "            r2 = right\n",
    "            while left < right:\n",
    "                if left & 1:\n",
    "                    self._all_apply(left, f)\n",
    "                    left += 1\n",
    "                if right & 1:\n",
    "                    right -= 1\n",
    "                    self._all_apply(right, f)\n",
    "                left >>= 1\n",
    "                right >>= 1\n",
    "            left = l2\n",
    "            right = r2\n",
    "\n",
    "            for i in range(1, self._log + 1):\n",
    "                if ((left >> i) << i) != left:\n",
    "                    self._update(left >> i)\n",
    "                if ((right >> i) << i) != right:\n",
    "                    self._update((right - 1) >> i)\n",
    "\n",
    "    def max_right(\n",
    "            self, left: int, g: typing.Callable[[typing.Any], bool]) -> int:\n",
    "        assert 0 <= left <= self._n\n",
    "        assert g(self._e)\n",
    "\n",
    "        if left == self._n:\n",
    "            return self._n\n",
    "\n",
    "        left += self._size\n",
    "        for i in range(self._log, 0, -1):\n",
    "            self._push(left >> i)\n",
    "\n",
    "        sm = self._e\n",
    "        first = True\n",
    "        while first or (left & -left) != left:\n",
    "            first = False\n",
    "            while left % 2 == 0:\n",
    "                left >>= 1\n",
    "            if not g(self._op(sm, self._d[left])):\n",
    "                while left < self._size:\n",
    "                    self._push(left)\n",
    "                    left *= 2\n",
    "                    if g(self._op(sm, self._d[left])):\n",
    "                        sm = self._op(sm, self._d[left])\n",
    "                        left += 1\n",
    "                return left - self._size\n",
    "            sm = self._op(sm, self._d[left])\n",
    "            left += 1\n",
    "\n",
    "        return self._n\n",
    "\n",
    "    def min_left(self, right: int, g: typing.Any) -> int:\n",
    "        assert 0 <= right <= self._n\n",
    "        assert g(self._e)\n",
    "\n",
    "        if right == 0:\n",
    "            return 0\n",
    "\n",
    "        right += self._size\n",
    "        for i in range(self._log, 0, -1):\n",
    "            self._push((right - 1) >> i)\n",
    "\n",
    "        sm = self._e\n",
    "        first = True\n",
    "        while first or (right & -right) != right:\n",
    "            first = False\n",
    "            right -= 1\n",
    "            while right > 1 and right % 2:\n",
    "                right >>= 1\n",
    "            if not g(self._op(self._d[right], sm)):\n",
    "                while right < self._size:\n",
    "                    self._push(right)\n",
    "                    right = 2 * right + 1\n",
    "                    if g(self._op(self._d[right], sm)):\n",
    "                        sm = self._op(self._d[right], sm)\n",
    "                        right -= 1\n",
    "                return right + 1 - self._size\n",
    "            sm = self._op(self._d[right], sm)\n",
    "\n",
    "        return 0\n",
    "\n",
    "    def _update(self, k: int) -> None:\n",
    "        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])\n",
    "\n",
    "    def _all_apply(self, k: int, f: typing.Any) -> None:\n",
    "        self._d[k] = self._mapping(f, self._d[k])\n",
    "        if k < self._size:\n",
    "            self._lz[k] = self._composition(f, self._lz[k])\n",
    "\n",
    "    def _push(self, k: int) -> None:\n",
    "        self._all_apply(2 * k, self._lz[k])\n",
    "        self._all_apply(2 * k + 1, self._lz[k])\n",
    "        self._lz[k] = self._id\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    " \n",
    "        op = lambda a,b: a+b\n",
    "        e = 0\n",
    "        mapping = lambda f,x: f*x\n",
    "        composition = lambda f,g: f*g\n",
    "        id_ = 1\n",
    "        f = -1\n",
    "        \n",
    "        st = LazySegTree(op, e, mapping, composition, id_, [x if x == 1 else -1 for x in nums1])\n",
    "\n",
    "        n = len(nums1)\n",
    "            \n",
    "        res = []\n",
    "        cursum = sum(nums2)\n",
    "        \n",
    "        for i,a,b in queries:\n",
    "            if i == 1:\n",
    "                st.apply(a, b+1, f)\n",
    "            if i == 2:\n",
    "                diff = st.all_prod()\n",
    "                pos = (n + diff) // 2\n",
    "                cursum += (pos) * a\n",
    "            if i == 3:\n",
    "                res.append(cursum)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTreeRangeUpdateXORSum:\n",
    "    def __init__(self, n):\n",
    "        # 模板：区间值01翻转与区间和查询\n",
    "        self.n = n\n",
    "        self.cover = [0] * (4 * self.n)  # 区间和\n",
    "        self.lazy = [0] * (4 * self.n)  # 懒标记\n",
    "        return\n",
    "    \n",
    "    def build(self, nums) -> None:\n",
    "        # 使用数组初始化线段树\n",
    "        stack = [[0, self.n - 1, 1]]\n",
    "        while stack:\n",
    "            s, t, i = stack.pop()\n",
    "            if i >= 0:\n",
    "                if s == t:\n",
    "                    self.cover[i] = nums[s]\n",
    "                else:\n",
    "                    stack.append([s, t, ~i])\n",
    "                    m = s + (t - s) // 2\n",
    "                    stack.append([s, m, 2 * i])\n",
    "                    stack.append([m + 1, t, 2 * i + 1])\n",
    "            else:\n",
    "                i = ~i\n",
    "                self.cover[i] = self.cover[2 * i] + self.cover[2 * i + 1]\n",
    "        return\n",
    "    \n",
    "    \n",
    "    def push_down(self, i: int, s: int, m: int, t: int) -> None:\n",
    "        if self.lazy[i]:\n",
    "            self.cover[2 * i] = m - s + 1 - self.cover[2 * i]\n",
    "            self.cover[2 * i + 1] = t - m - self.cover[2 * i + 1]\n",
    "\n",
    "            self.lazy[2 * i] ^= self.lazy[i]  # 注意使用异或抵消查询\n",
    "            self.lazy[2 * i + 1] ^= self.lazy[i]  # 注意使用异或抵消查询\n",
    "\n",
    "            self.lazy[i] = 0\n",
    "        return\n",
    "\n",
    "    def update(self, left: int, right: int, s: int, t: int, val: int, i: int) -> None:\n",
    "        # 增减区间值 left 与 right 取值为 0 到 n-1 而 i 从 1 开始\n",
    "        stack = [[s, t, i]]\n",
    "        while stack:\n",
    "            s, t, i = stack.pop()\n",
    "            if i >= 0:\n",
    "                if left <= s and t <= right:\n",
    "                    self.cover[i] = t - s + 1 - self.cover[i]\n",
    "                    self.lazy[i] ^= val  # 注意使用异或抵消查询\n",
    "                    continue\n",
    "\n",
    "                m = s + (t - s) // 2\n",
    "                self.push_down(i, s, m, t)\n",
    "                stack.append([s, t, ~i])\n",
    "\n",
    "                if left <= m:  # 注意左右子树的边界与范围\n",
    "                    stack.append([s, m, 2 * i])\n",
    "                if right > m:\n",
    "                    stack.append([m + 1, t, 2 * i + 1])\n",
    "            else:\n",
    "                i = ~i\n",
    "                self.cover[i] = self.cover[2 * i] + self.cover[2 * i + 1]\n",
    "        return\n",
    "\n",
    "    def query_sum(self, left: int, right: int, s: int, t: int, i: int) -> int:\n",
    "        # 查询区间的和\n",
    "        stack = [[s, t, i]]\n",
    "        ans = 0\n",
    "        while stack:\n",
    "            s, t, i = stack.pop()\n",
    "            if left <= s and t <= right:\n",
    "                ans += self.cover[i]\n",
    "                continue\n",
    "            m = s + (t - s) // 2\n",
    "            self.push_down(i, s, m, t)\n",
    "            if left <= m:\n",
    "                stack.append([s, m, 2 * i])\n",
    "            if right > m:\n",
    "                stack.append([m + 1, t, 2 * i + 1])\n",
    "        return ans\n",
    "    \n",
    "    \n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        tree = SegmentTreeRangeUpdateXORSum(n)\n",
    "        tree.build(nums1)\n",
    "        ans = []\n",
    "        s = sum(nums2)\n",
    "        for op, x, y in queries:\n",
    "            if op == 1:\n",
    "                tree.update(x, y, 0, n-1, 1, 1)\n",
    "            elif op == 2:\n",
    "                s += tree.query_sum(0, n-1, 0, n-1, 1)*x\n",
    "            else:\n",
    "                ans.append(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        n = len(nums1)\n",
    "        seg = LazySegmentTree(nums1)\n",
    "        tot = sum(nums2)\n",
    "        for t, x, y in queries:\n",
    "            if t == 1: seg.update(x, y)\n",
    "            elif t == 2: tot += seg.query(0, n-1) * x\n",
    "            else: ans.append(tot)\n",
    "        return ans\n",
    "\n",
    "class LazySegmentTree:\n",
    "    def __init__(self, nums):\n",
    "        self.n = len(nums)\n",
    "        self.nums = nums\n",
    "        self.ones = [0] * (4 * self.n)\n",
    "        self.lazy = [True] * (4 * self.n)\n",
    "        self._build(0, 0, self.n-1)\n",
    "\n",
    "    def _build(self, tree_index, l, r):\n",
    "        if l == r:\n",
    "            self.ones[tree_index] = self.nums[l]\n",
    "            return\n",
    "        left, right = 2 * tree_index + 1, 2 * tree_index + 2\n",
    "        mid = (l + r) // 2\n",
    "        self._build(left, l, mid)\n",
    "        self._build(right, mid+1, r)\n",
    "        self.ones[tree_index] = self.ones[left] + self.ones[right]\n",
    "\n",
    "    def update(self, ql, qr):\n",
    "        self._update(0, 0, self.n-1, ql, qr)\n",
    "\n",
    "    def _update(self, tree_index, l, r, ql, qr):\n",
    "        if l == ql and r == qr:\n",
    "            self.lazy[tree_index] = not self.lazy[tree_index]\n",
    "            ones = self.ones[tree_index]\n",
    "            zeros = r - l + 1 - ones\n",
    "            self.ones[tree_index] = zeros\n",
    "            return\n",
    "        left, right = 2 * tree_index + 1, 2 * tree_index + 2\n",
    "        mid = (l + r) // 2\n",
    "        if not self.lazy[tree_index]:\n",
    "            self._update(left, l, mid, l, mid)\n",
    "            self._update(right, mid+1, r, mid+1, r)\n",
    "            self.lazy[tree_index] = True\n",
    "        if qr <= mid: self._update(left, l, mid, ql, qr)\n",
    "        elif ql > mid: self._update(right, mid+1, r, ql, qr)\n",
    "        else:\n",
    "            self._update(left, l, mid, ql, mid)\n",
    "            self._update(right, mid+1, r, mid+1, qr)\n",
    "        self.ones[tree_index] = self.ones[left] + self.ones[right]\n",
    "\n",
    "    def query(self, ql, qr):\n",
    "        return self._query(0, 0, self.n-1, ql, qr)\n",
    "\n",
    "    def _query(self, tree_index, l, r, ql, qr):\n",
    "        if l == ql and r == qr:\n",
    "            return self.ones[tree_index]\n",
    "        left, right = 2 * tree_index + 1, 2 * tree_index + 2\n",
    "        mid = (l + r) // 2\n",
    "        if not self.lazy[tree_index]:\n",
    "            self._update(left, l, mid, l, mid)\n",
    "            self._update(right, mid+1, r, mid+1, r)\n",
    "            self.lazy[tree_index] = True\n",
    "        if qr <= mid: return self._query(left, l, mid, ql, qr)\n",
    "        if ql > mid: return self._query(right, mid+1, r, ql, qr)\n",
    "        ones1 = self._query(left, l, mid, ql, mid)\n",
    "        ones2 = self._query(right, mid+1, r, mid+1, qr)\n",
    "        return ones1 + ones2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class LazySegmentTree:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.n = len(nums)\n",
    "        self.nums = nums\n",
    "        self.tree = [0] * (4 * self.n)\n",
    "        self.tag = [0] * (4 * self.n)\n",
    "        self._build(1, 0, self.n - 1)\n",
    "\n",
    "    def _build(self, o: int, l: int, r: int) -> None:\n",
    "        if l == r:\n",
    "            self.tree[o] = self.nums[l]\n",
    "            return\n",
    "        mid = (l + r) // 2\n",
    "        lo, hi = 2 * o, 2 * o + 1\n",
    "        self._build(lo, l, mid)\n",
    "        self._build(hi, mid + 1, r)\n",
    "        self.push_up(o)\n",
    "\n",
    "    def push_up(self, o: int) -> None:\n",
    "        self.tree[o] = self.tree[2 * o] + self.tree[2 * o + 1]\n",
    "\n",
    "    def push_down(self, o: int, l: int, r: int) -> None:\n",
    "        if not self.tag[o]:\n",
    "            return\n",
    "        mid = (l + r) // 2\n",
    "        lo, hi = 2 * o, 2 * o + 1\n",
    "        self.add_tag(lo, l, mid, self.tag[o])\n",
    "        self.add_tag(hi, mid + 1, r, self.tag[o])\n",
    "        self.tag[o] = 0\n",
    "\n",
    "    def add_tag(self, o: int, l, r, k) -> None:\n",
    "        self.tag[o] ^= 1\n",
    "        self.tree[o] = (r - l + 1) - self.tree[o]\n",
    "\n",
    "    def _update(self, o: int, l: int, r: int, L: int, R: int, V) -> None:\n",
    "        if L <= l and r <= R:\n",
    "            self.add_tag(o, l, r, V)\n",
    "            return\n",
    "        self.push_down(o, l, r)\n",
    "        lo, hi = 2 * o, 2 * o + 1\n",
    "        mid = (l + r) // 2\n",
    "        if L <= mid:\n",
    "            self._update(lo, l, mid, L, R, V)\n",
    "        if mid < R:\n",
    "            self._update(hi, mid + 1, r, L, R, V)\n",
    "        self.push_up(o)\n",
    "\n",
    "    def _query(self, o: int, l: int, r: int, L: int, R: int) -> int:\n",
    "        if L <= l and r <= R:\n",
    "            return self.tree[o]\n",
    "        left, right = 2 * o, 2 * o + 1\n",
    "        mid = (l + r) // 2\n",
    "        self.push_down(o, l, r)\n",
    "        ans = 0\n",
    "        if L <= mid:\n",
    "            ans += self._query(left, l, mid, L, R)\n",
    "        if mid < R:\n",
    "            ans += self._query(right, mid + 1, r, L, R)\n",
    "        return ans\n",
    "\n",
    "    def update(self, L: int, R: int, V: int) -> None:\n",
    "        self._update(1, 0, self.n - 1, L, R, V)\n",
    "\n",
    "    def query(self, L: int, R: int) -> int:\n",
    "        return self._query(1, 0, self.n - 1, L, R)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(\n",
    "        self, nums1: List[int], nums2: List[int], queries: List[List[int]]\n",
    "    ) -> List[int]:\n",
    "        ans = sum(nums2)\n",
    "        n = len(nums1)\n",
    "        ret = []\n",
    "        seg = LazySegmentTree(nums1)\n",
    "        for op, x, y in queries:\n",
    "            if op == 1:\n",
    "                seg.update(x, y, 1)\n",
    "                #for i in range(n): print(seg.query(i, i), end=' ')\n",
    "                #print(seg.query(0, 2))\n",
    "            elif op == 2:\n",
    "                now = seg.query(0, n - 1)\n",
    "                ans += now * x\n",
    "            else:\n",
    "                ret.append(ans)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        cnt = [0] * (4 * n)\n",
    "        flip = [0] * (4 * n)\n",
    "        def build(idx, l, r):\n",
    "            if l == r:\n",
    "                cnt[idx] = nums1[l - 1]\n",
    "                return\n",
    "            m = l + r >> 1\n",
    "            build(idx << 1, l, m)\n",
    "            build(idx << 1 | 1, m + 1, r)\n",
    "            cnt[idx] = cnt[idx << 1] + cnt[idx << 1 | 1]\n",
    "\n",
    "        def do(idx, l, r):\n",
    "            cnt[idx] = r - l + 1 - cnt[idx]\n",
    "            flip[idx] ^= 1\n",
    "\n",
    "        def update(idx, l, r, left, right):\n",
    "            if l >= left and r <= right:\n",
    "                do(idx, l, r)\n",
    "                return\n",
    "            m = l + r >> 1\n",
    "            if flip[idx]:\n",
    "                flip[idx] = 0\n",
    "                do(idx << 1, l, m)\n",
    "                do(idx << 1 | 1, m + 1, r)\n",
    "            \n",
    "            if m >= left:\n",
    "                update(idx << 1, l, m, left, right)\n",
    "            if m < right:\n",
    "                update(idx << 1 | 1, m + 1, r, left, right)\n",
    "            cnt[idx] = cnt[idx << 1] + cnt[idx << 1 | 1]\n",
    "            \n",
    "        ret = []\n",
    "        build(1, 1, n)\n",
    "        s = sum(nums2)\n",
    "        for a, b, c in queries:\n",
    "            if a == 1:\n",
    "                update(1, 1, n, b + 1, c + 1)\n",
    "            elif a == 2:\n",
    "                s += b * cnt[1]\n",
    "            else:\n",
    "                ret.append(s)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        sm = sum(nums2)\n",
    "        end = 4 * n\n",
    "        data = [0] * end\n",
    "        lazy = [False] * end\n",
    "\n",
    "        def build(o, l, r):\n",
    "            if l == r:\n",
    "                data[o] = nums1[l]\n",
    "                return\n",
    "            mid = (l + r) // 2\n",
    "            build(o * 2 + 1, l, mid)\n",
    "            build(o * 2 + 2, mid + 1, r)\n",
    "            data[o] = data[o*2 + 1] + data[o*2 + 2]\n",
    "\n",
    "        def pushDown(o, l, r):\n",
    "            if lazy[o] == False:\n",
    "                return\n",
    "            lazy[o*2+1] = not lazy[o*2+1]\n",
    "            lazy[o*2+2] = not lazy[o*2+2]\n",
    "            lazy[o] = False\n",
    "            mid = (l + r) // 2\n",
    "            data[o*2+1] = (mid - l + 1) - data[o*2+1]\n",
    "            data[o*2+2] = (r - mid) - data[o*2+2]\n",
    "\n",
    "        def update(o, l, r, L, R):\n",
    "            if L <= l and r <= R:\n",
    "                data[o] = (r - l + 1) - data[o]\n",
    "                lazy[o] = not lazy[o]\n",
    "                return\n",
    "            pushDown(o, l, r)\n",
    "            mid = (l + r) // 2\n",
    "            if L <= mid:\n",
    "                update(o * 2 + 1, l, mid, L, R)\n",
    "            if mid < R:\n",
    "                update(o * 2 + 2, mid + 1, r, L, R)\n",
    "            data[o] = data[o*2+1] + data[o*2+2]\n",
    "\n",
    "        build(0, 0, n-1)\n",
    "        ans = []\n",
    "        for op, l, r in queries:\n",
    "            if op == 1:\n",
    "                update(0, 0, n-1, l, r)\n",
    "            elif op == 2:\n",
    "                sm += l * data[0]\n",
    "            else:\n",
    "                ans.append(sm)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        '''\n",
    "        # 直接遍历超时\n",
    "        res = []\n",
    "        length = len(nums1)\n",
    "        for q, l, r in queries:\n",
    "            if q == 1:          # 操作1\n",
    "                for j in range(l, r+1):\n",
    "                    nums1[j] = 0 if nums1[j] else 1\n",
    "            elif q == 2:        # 操作 2\n",
    "                for i in range(length):\n",
    "                    nums2[i] += nums1[i] * l \n",
    "            else:               # 操作 3\n",
    "                res.append(sum(nums2))\n",
    "        return res\n",
    "        '''\n",
    "        n = len(nums1)\n",
    "        cnt1 = [0] * (4 * n)\n",
    "        flip = [False] * (4 * n)\n",
    "\n",
    "        # 维护区间 1 的个数\n",
    "        def maintain(p):\n",
    "            cnt1[p] = cnt1[p*2] + cnt1[p*2 + 1]\n",
    "        \n",
    "        # 执行区间反转\n",
    "        def do(p, l, r):\n",
    "            cnt1[p] = r - l + 1 - cnt1[p]\n",
    "            flip[p] = not flip[p]\n",
    "        \n",
    "        # 初始化线段树 p, l, r = 1, 1, n\n",
    "        def build(p, l, r):\n",
    "            if l == r:\n",
    "                cnt1[p] = nums1[l-1]\n",
    "                return \n",
    "            m = (l+r) // 2\n",
    "            build(p*2, l, m)\n",
    "            build(p*2+1, m+1, r)\n",
    "            maintain(p)\n",
    "        \n",
    "        # 反转区间 [L, R] p, l, r = 1, 1, n\n",
    "        def update(p, l, r, L, R):\n",
    "            if L <= l and r <= R:\n",
    "                do(p, l, r)\n",
    "                return\n",
    "            m = (l+r) // 2\n",
    "            if flip[p]:\n",
    "                do(p*2, l, m)\n",
    "                do(p*2+1, m +1, r)\n",
    "                flip[p] = False\n",
    "            if m >= L: update(p * 2, l, m, L, R)\n",
    "            if m < R: update(p*2+1, m+1, r, L, R)\n",
    "            maintain(p)\n",
    "        \n",
    "        build(1, 1, n)\n",
    "        ans, s = [], sum(nums2)\n",
    "        for op, l, r in queries:\n",
    "            if op == 1: update(1, 1, n, l+1, r+1)\n",
    "            elif op == 2: s += l * cnt1[1]\n",
    "            else: ans.append(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        cnt1 = [0] * (4 * n)\n",
    "        flip = [False] * (4 * n)\n",
    "\n",
    "        # 维护区间 1 的个数\n",
    "        def maintain(o: int) -> None:\n",
    "            cnt1[o] = cnt1[o * 2] + cnt1[o * 2 + 1]\n",
    "\n",
    "        # 执行区间反转\n",
    "        def do(o: int, l: int, r: int) -> None:\n",
    "            cnt1[o] = r - l + 1 - cnt1[o]\n",
    "            flip[o] = not flip[o]\n",
    "\n",
    "        # 初始化线段树   o,l,r=1,1,n\n",
    "        def build(o: int, l: int, r: int) -> None:\n",
    "            if l == r:\n",
    "                cnt1[o] = nums1[l - 1]\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            build(o * 2, l, m)\n",
    "            build(o * 2 + 1, m + 1, r)\n",
    "            maintain(o)\n",
    "\n",
    "        # 反转区间 [L,R]   o,l,r=1,1,n\n",
    "        def update(o: int, l: int, r: int, L: int, R: int) -> None:\n",
    "            if L <= l and r <= R:\n",
    "                do(o, l, r)\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            if flip[o]:\n",
    "                do(o * 2, l, m)\n",
    "                do(o * 2 + 1, m + 1, r)\n",
    "                flip[o] = False\n",
    "            if m >= L: update(o * 2, l, m, L, R)\n",
    "            if m < R: update(o * 2 + 1, m + 1, r, L, R)\n",
    "            maintain(o)\n",
    "\n",
    "        build(1, 1, n)\n",
    "        ans, s = [], sum(nums2)\n",
    "        for op, l, r in queries:\n",
    "            if op == 1: update(1, 1, n, l + 1, r + 1)\n",
    "            elif op == 2: s += l * cnt1[1]\n",
    "            else: ans.append(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        cnt1 = [0] * (4 * n)\n",
    "        flip = [False] * (4 * n)\n",
    "\n",
    "        def maintain(o):\n",
    "            cnt1[o] = cnt1[2 * o] + cnt1[2 * o + 1]\n",
    "        \n",
    "        def do(o, l, r):\n",
    "            cnt1[o] = r - l + 1 - cnt1[o]\n",
    "            flip[o] = not flip[o]\n",
    "        \n",
    "        def build(o, l, r):\n",
    "            if l == r:\n",
    "                cnt1[o] = nums1[l - 1]\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            build(2 * o, l, m)\n",
    "            build(2 * o + 1, m + 1, r)\n",
    "            maintain(o)\n",
    "        \n",
    "        def update(o, l, r, L, R):\n",
    "            if L <= l and r <= R:\n",
    "                do(o, l, r)\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            if flip[o]:\n",
    "                do(2 * o, l, m)\n",
    "                do(2 * o + 1, m + 1, r)\n",
    "                flip[o] = False\n",
    "            if L <= m:\n",
    "                update(2 * o, l, m, L, R)\n",
    "            if R > m:\n",
    "                update(2 * o + 1, m + 1, r, L, R)\n",
    "            maintain(o)\n",
    "        \n",
    "        build(1, 1, n)\n",
    "        res, s = [], sum(nums2)\n",
    "        for op, l, r in queries:\n",
    "            if op == 1:\n",
    "                update(1, 1, n, l + 1, r + 1)\n",
    "            elif op == 2:\n",
    "                s += l * cnt1[1]\n",
    "            else:\n",
    "                res.append(s)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        #更新一个子数组的值，把子数组内的元素取反\n",
    "        # 查询一个子数组的值，求和\n",
    "        # lazy更新，延迟更新\n",
    "        #lazy_tag: 用一个数组维护每个区间需要更新的值。\n",
    "        n=len(nums1)\n",
    "        todo=[False]*4*n\n",
    "        cnt1=[0]*4*n\n",
    "        def maintain(o):\n",
    "            cnt1[o]=cnt1[o*2]+cnt1[o*2+1]\n",
    "            return\n",
    "\n",
    "\n",
    "        def build(o,l,r):\n",
    "            if l==r:\n",
    "                cnt1[o]=nums1[l-1]\n",
    "                return\n",
    "\n",
    "            m=(l+r)//2\n",
    "            build(o*2,l,m)\n",
    "            build(o*2+1,m+1,r)\n",
    "            maintain(o)\n",
    "\n",
    "        def do(o,l,r): # 执行区间反转\n",
    "            cnt1[o]=r-l+1-cnt1[o]\n",
    "            todo[o]=not todo[o]\n",
    "\n",
    "\n",
    "        def update(o,l,r,L,R): #翻转区间[L，R]\n",
    "            if L<=l and R>=r:\n",
    "                do(o,l,r)\n",
    "                return\n",
    "            m=(l+r)//2\n",
    "            if todo[o]:\n",
    "                do(o*2,l,m)\n",
    "                do(o*2+1,m+1,r)\n",
    "                todo[o]=False\n",
    "\n",
    "            if m>=L:\n",
    "                update(o*2,l,m,L,R)\n",
    "            if m+1<=R:\n",
    "                update(o*2+1,m+1,r,L,R)\n",
    "            maintain(o)\n",
    "                #维护\n",
    "        build(1,1,n)\n",
    "        ans=[]\n",
    "        s=sum(nums2)\n",
    "        for op,l,r in queries:\n",
    "            if op==1: update(1,1,n,l+1,r+1)\n",
    "            elif op==2: s+=l*cnt1[1]\n",
    "            else: ans.append(s)\n",
    "        return ans \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "\n",
    "        cnt1 = [0] * (4 * n)\n",
    "        flip = [False] * (4 * n)\n",
    "        def maintain(o: int) -> None:\n",
    "            cnt1[o] = cnt1[2* o] + cnt1[2 * o +  1]\n",
    "\n",
    "\n",
    "        def build(o: int, l: int, r: int) -> None:\n",
    "            if l == r:\n",
    "                cnt1[o] = nums1[l - 1]        \n",
    "                return \n",
    "            \n",
    "            m = (l + r) // 2\n",
    "            build(o * 2, l, m)\n",
    "            build(o * 2 + 1, m + 1, r)\n",
    "\n",
    "            maintain(o)\n",
    "\n",
    "        def do(o: int, l: int, r: int) -> None:\n",
    "            cnt1[o] = r - l + 1 - cnt1[o]\n",
    "            flip[o] = not flip[o]\n",
    "\n",
    "        def update(o: int, l: int, r: int, L:int, R: int) -> None:\n",
    "            \n",
    "            if L <= l and R >= r:\n",
    "                do(o, l, r)\n",
    "                return\n",
    "\n",
    "            m = (l + r) //2\n",
    "            if flip[o]:\n",
    "                do(o * 2, l, m)\n",
    "                do(o * 2 + 1, m + 1, r)\n",
    "                flip[o] = False\n",
    "\n",
    "\n",
    "\n",
    "            if m >= L: update(o * 2,l, m, L, R)\n",
    "            if m < R: update(o * 2 + 1, m+ 1, r, L, R)\n",
    "\n",
    "            maintain(o)\n",
    "        \n",
    "        build(1, 1, n)\n",
    "\n",
    "        ans, s = [], sum(nums2)\n",
    "\n",
    "        for op, l, r in queries:\n",
    "            if op == 1: update(1,1,n, l+ 1, r + 1)\n",
    "            elif op == 2: s += l * cnt1[1]\n",
    "            else: ans.append(s)\n",
    "        return ans      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        node = [0] * (4 * n)\n",
    "        # 懒标记：True表示该节点代笔的区间被曾经被修改，但是其子节点尚未更新\n",
    "        lazy = [False] * (4 * n)\n",
    "\n",
    "        # 初始化线段树\n",
    "        def build(i, l, r) -> None:\n",
    "            if l == r:\n",
    "                # 初始化赋值\n",
    "                node[i] = nums1[l - 1]\n",
    "                return \n",
    "            mid = (l + r) >> 1\n",
    "            build(i * 2, l, mid)\n",
    "            build(i * 2 + 1, mid + 1, r)\n",
    "            # 维护区间 [l, r] 的值\n",
    "            node[i] = node[i * 2] + node[i * 2 + 1]\n",
    "        \n",
    "        # 更新节点值，并设置lazy标记\n",
    "        def do(i, l, r) -> None:\n",
    "            node[i] = r - l + 1 - node[i]\n",
    "            lazy[i] = not lazy[i]\n",
    "\n",
    "        # 区间更新：本题中更新区间[l, r] 相当于做翻转\n",
    "        def update(i, l, r, L, R) -> None:\n",
    "            if L <= l and R >= r:\n",
    "                # 区间更新\n",
    "                do(i, l, r)\n",
    "                return\n",
    "            \n",
    "            mid = (l + r) >> 1\n",
    "            if lazy[i]:\n",
    "                # 根据标记信息更新p的两个左右子节点，同时为子节点增加标记\n",
    "                # 然后清除当前节点的标记\n",
    "                do(i * 2, l, mid)\n",
    "                do(i * 2 + 1, mid + 1, r)\n",
    "                lazy[i] = False\n",
    "            \n",
    "            if L <= mid:\n",
    "                update(i * 2, l, mid, L, R)\n",
    "            if R > mid:\n",
    "                update(i * 2 + 1, mid + 1, r, L, R)\n",
    "            \n",
    "            # 更新节点值\n",
    "            node[i] = node[i * 2] + node[i * 2 + 1]\n",
    "    \n",
    "        build(1, 1, n)\n",
    "        res, s = [], sum(nums2)\n",
    "        for op, L, R in queries:\n",
    "            if op == 1:\n",
    "                update(1, 1, n, L + 1, R + 1)\n",
    "            elif op == 2:\n",
    "                s += L * node[1]\n",
    "            else:\n",
    "                res.append(s)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        cnt1 = [0]*(4*n)\n",
    "        todo = [False]*(4*n)\n",
    "        def maintain(o):\n",
    "            cnt1[o] = cnt1[o*2]+cnt1[o*2+1] \n",
    "        def bulid(o,l,r):\n",
    "            if l==r:\n",
    "                cnt1[o] = nums1[l-1]\n",
    "                return\n",
    "            m = (l+r)//2\n",
    "            bulid(2*o,l,m)\n",
    "            bulid(2*o+1,m+1,r)\n",
    "            maintain(o)\n",
    "        def do(o,l,r):\n",
    "            cnt1[o] = r-l+1-cnt1[o]\n",
    "            todo[o] = not todo[o]\n",
    "        def update(o,l,r,L,R):\n",
    "            if L<=l and R>=r:\n",
    "                do(o,l,r)\n",
    "                return\n",
    "            m = (l+r)//2\n",
    "            if todo[o]:\n",
    "                do(o*2,l,m)\n",
    "                do(o*2+1,m+1,r)\n",
    "                todo[o] = False\n",
    "            if m>=L:\n",
    "                update(2*o,l,m,L,R)\n",
    "            if m<R:\n",
    "                update(2*o+1,m+1,r,L,R)\n",
    "            maintain(o)\n",
    "\n",
    "        bulid(1,1,n)\n",
    "        ans = []\n",
    "        s= sum(nums2)\n",
    "        for op,l,r in queries:\n",
    "            if op==1:\n",
    "                update(1,1,n,l+1,r+1)\n",
    "            elif op ==2:\n",
    "                s+=l*cnt1[1]\n",
    "            else: ans.append(s)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        sm = sum(nums2)\n",
    "        end = 4 * n\n",
    "        data = [0] * end\n",
    "        lazy = [False] * end\n",
    "\n",
    "        def build(o, l, r):\n",
    "            if l == r:\n",
    "                data[o] = nums1[l]\n",
    "                return\n",
    "            mid = (l + r) // 2\n",
    "            build(o * 2 + 1, l, mid)\n",
    "            build(o * 2 + 2, mid + 1, r)\n",
    "            data[o] = data[o*2 + 1] + data[o*2 + 2]\n",
    "\n",
    "        def pushDown(o, l, r):\n",
    "            if lazy[o] == False:\n",
    "                return\n",
    "            lazy[o*2+1] = not lazy[o*2+1]\n",
    "            lazy[o*2+2] = not lazy[o*2+2]\n",
    "            lazy[o] = False\n",
    "            mid = (l + r) // 2\n",
    "            data[o*2+1] = (mid - l + 1) - data[o*2+1]\n",
    "            data[o*2+2] = (r - mid) - data[o*2+2]\n",
    "\n",
    "        def update(o, l, r, L, R):\n",
    "            if L <= l and r <= R:\n",
    "                data[o] = (r - l + 1) - data[o]\n",
    "                lazy[o] = not lazy[o]\n",
    "                return\n",
    "            pushDown(o, l, r)\n",
    "            mid = (l + r) // 2\n",
    "            if L <= mid:\n",
    "                update(o * 2 + 1, l, mid, L, R)\n",
    "            if mid < R:\n",
    "                update(o * 2 + 2, mid + 1, r, L, R)\n",
    "            data[o] = data[o*2+1] + data[o*2+2]\n",
    "\n",
    "        def query(o, l, r, L, R):\n",
    "            if L <= l and r <= R:\n",
    "                return data[o]\n",
    "            pushDown(o, l, r)\n",
    "            mid = (l + r) // 2\n",
    "            ans = 0\n",
    "            if L <= mid:\n",
    "                ans += query(o * 2 + 1, l, mid, L, R)\n",
    "            if mid < R:\n",
    "                ans += query(o * 2 + 2, mid + 1, r, L, R)\n",
    "            return ans\n",
    "\n",
    "        build(0, 0, n-1)\n",
    "        ans = []\n",
    "        for op, l, r in queries:\n",
    "            if op == 1:\n",
    "                update(0, 0, n-1, l, r)\n",
    "            elif op == 2:\n",
    "                #sm += l * data[0]\n",
    "                sm += l * query(0, 0, n-1, 0, n-1)\n",
    "            else:\n",
    "                ans.append(sm)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        cnt1 = [0] * (4 * n)\n",
    "        todo = [False] * (4 * n)\n",
    "\n",
    "        def maintain(o: int):\n",
    "            cnt1[o] = cnt1[o * 2] + cnt1[o * 2 + 1]\n",
    "\n",
    "        def do(o: int, l: int, r: int):\n",
    "            cnt1[o] = r - l + 1 - cnt1[o]\n",
    "            todo[o] = not todo[o]\n",
    "\n",
    "        def build(o: int, l: int, r: int) -> None:\n",
    "            if l == r:\n",
    "                cnt1[o] = nums1[l - 1]\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            build(o * 2, l, m)\n",
    "            build(o * 2 + 1, m + 1, r)\n",
    "            maintain(o)\n",
    "\n",
    "        def update(o: int, l: int, r: int, L: int, R: int) -> None:\n",
    "            if L <= l and r <= R:\n",
    "                do(o, l, r)\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            if todo[o]:\n",
    "                do(o * 2, l, m)\n",
    "                do(o * 2 + 1, m+1, r)\n",
    "                todo[o] = False\n",
    "            if m >= L: update(o * 2, l, m, L, R)\n",
    "            if m+1 <= R: update(o * 2 + 1, m+1, r, L, R)\n",
    "            maintain(o)\n",
    "\n",
    "        build(1, 1, n)\n",
    "        ans, s = [], sum(nums2)\n",
    "        for op, l, r in queries:\n",
    "            if op == 1:\n",
    "                update(1, 1, n, l+1, r+1)\n",
    "            elif op == 2:\n",
    "                s += l * cnt1[1]\n",
    "            else:\n",
    "                ans.append(s)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 操作1：将 nums1 的 [l,r] 的 0/1 翻转\n",
    "        # 操作3：输出 nums2 的和\n",
    "        # 所以 nums2 每一个值是多少并不重要，关注 nums2 的和（用一个变量记录）\n",
    "        # 操作2的作用就是将 nums1 的和的 p 倍加到 nums2 的和上去\n",
    "        # cnt1[o]：编号为 o 的节点的区间1的个数\n",
    "        # flip[o]：编号为 o 的节点的区间里是否进行了 0/1 翻转\n",
    "        n = len(nums1)\n",
    "        cnt1 = [0] * (4 * n)\n",
    "        flip = [False] * (4 * n)\n",
    "\n",
    "        def maintain(o: int) -> int:\n",
    "            # 计算节点编号为 o 所代表的区间里有多少1\n",
    "            # 也就是节点 o 的左右儿子的 cnt1 和\n",
    "            # 在 build 和 update 的时候用\n",
    "            cnt1[o] = cnt1[o * 2] + cnt1[o * 2 + 1]\n",
    "\n",
    "        def build(o: int, l: int, r: int) -> None:\n",
    "            # o：当前节点编号；l，r:当前节点的区间范围\n",
    "            if l == r:  # 当区间长度只有1的时候，停止递归\n",
    "                # 这道题是要维护区间内有多少个1\n",
    "                # 所以当 l == r，cnt1[o] 就是对应 nums1 的值\n",
    "                # l-1 是因为在线段树里，区间下标从1开始\n",
    "                cnt1[o] = nums1[l - 1]\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            build(o * 2, l, m)  # 左儿子\n",
    "            build(o * 2 + 1, m + 1, r)  # 右儿子\n",
    "            maintain(o)\n",
    "\n",
    "        def do(o: int, l: int, r: int) -> None:\n",
    "            # 对编号为 o 的节点进行更新操作\n",
    "            # 在 update 里用\n",
    "            # 在这道题里\n",
    "            # 更新操作是操作1干的翻转 0/1\n",
    "            # 一个区间的 0/1 反转了，cnt1[0] 变为 区间长度 - 原来有多少个1\n",
    "            cnt1[o] = r - l + 1 - cnt1[o]\n",
    "            # flip[o] 取反即可\n",
    "            flip[o] = not flip[o]\n",
    "\n",
    "        def update(o: int, l: int, r: int, L: int, R: int) -> None:\n",
    "            # o：当前节点编号；\n",
    "            # l，r:当前节点的区间范围\n",
    "            # L,R：要更新的区间的范围\n",
    "            if l >= L and r <= R:\n",
    "                # 当前节点完全在要更新的区间范围里(区间内所有的点都要进行更新)\n",
    "                # 那就对这个节点进行操作之后就 return，不在继续递归下去\n",
    "                do(o, l, r)\n",
    "                return\n",
    "            # 没有进入上面这个 if-return，说明\n",
    "            # 这个节点的区间 [l,r] 包含了一些这次更新范围外的区间\n",
    "            # 还要递归下去\n",
    "            m = (l + r) // 2\n",
    "\n",
    "            # 先将更新标记传递下去，并将 o 的标记取消掉\n",
    "            # cnt1[o] 的修改在最后面，左右儿子递归完了再维护\n",
    "            if flip[o]:\n",
    "                do(o * 2, l, m)\n",
    "                do(o * 2 + 1, m + 1, r)\n",
    "                flip[o] = False\n",
    "\n",
    "            if not m < L:  # l<m<L ：左儿子没有要更新的区间，不用继续递归下去\n",
    "                update(o * 2, l, m, L, R)  # 左儿子\n",
    "            if not R < m + 1:  # R<m+1<r ：右儿子没有要更新的区间，不用继续递归下去\n",
    "                update(o * 2 + 1, m + 1, r, L, R)  # 右儿子\n",
    "            maintain(o)\n",
    "\n",
    "        build(1, 1, n)  # 初始化，第一个节点的编号为1，区间范围为[1,n]\n",
    "        ans, s = [], sum(nums2)\n",
    "        for op, l, r in queries:\n",
    "            if op == 1:\n",
    "                update(1, 1, n, l + 1, r + 1)  # +1因为下标从1开始\n",
    "            elif op == 2:  # [2,p,0] l==p\n",
    "                s += l * cnt1[1]  # cnt[1]代表nums1里有毒少个1\n",
    "            elif op == 3:\n",
    "                ans.append(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        #copy 0x3\n",
    "        n = len(nums1)\n",
    "        cnt1 = [0] *(4*n)\n",
    "        flip = [False] *(4*n)\n",
    "\n",
    "        def maintain(o):\n",
    "            cnt1[o] = cnt1[o*2] + cnt1[o*2+1]\n",
    "        \n",
    "        def do(o,l,r):\n",
    "            cnt1[o] = r-l+1-cnt1[o]\n",
    "            flip[o] = not flip[o]\n",
    "        \n",
    "        def build(o,l,r):\n",
    "            if l == r:\n",
    "                cnt1[o] = nums1[l-1]\n",
    "                return\n",
    "            m = (l+r)//2\n",
    "            build(o*2,l,m)\n",
    "            build(o*2+1,m+1,r)\n",
    "            maintain(o)\n",
    "        \n",
    "        def update(o,l,r,L,R):\n",
    "            if L <=l and r <=R:\n",
    "                do(o,l,r)\n",
    "                return\n",
    "            m = (l+r)//2\n",
    "            if flip[o]:\n",
    "                do(o*2,l,m)\n",
    "                do(o*2+1,m+1,r)\n",
    "                flip[o] = False\n",
    "            if m >=L:\n",
    "                update(o*2,l,m,L,R)\n",
    "            if m<R:\n",
    "                update(o*2+1,m+1,r,L,R)\n",
    "            maintain(o)\n",
    "        \n",
    "        build(1,1,n)\n",
    "        ans,s = [],sum(nums2)\n",
    "        for op,l,r in queries:\n",
    "            if op==1:\n",
    "                update(1,1,n,l+1,r+1)\n",
    "            elif op == 2:\n",
    "                s+=l*cnt1[1]\n",
    "            else:\n",
    "                ans.append(s)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "      n = len(nums1)\n",
    "      cnt1 = [0] * (4 * n)\n",
    "      flip = [False] * (4 * n)\n",
    "\n",
    "      def maintain(o: int):\n",
    "        cnt1[o] = cnt1[o * 2] + cnt1[o * 2 + 1]\n",
    "\n",
    "      def build(o: int, l: int, r: int):\n",
    "        if l == r:\n",
    "          cnt1[o] = nums1[l - 1]\n",
    "          return\n",
    "        m = (l + r) >> 1\n",
    "        build(o * 2, l, m)\n",
    "        build(o * 2 + 1, m + 1, r)\n",
    "        maintain(o)\n",
    "\n",
    "      def do(o: int, l: int, r: int):\n",
    "        cnt1[o] = r - l + 1 - cnt1[o]\n",
    "        flip[o] = not flip[o]\n",
    "\n",
    "      def update(o: int, l: int, r: int, L: int, R: int):\n",
    "        if L <= l and r <= R:\n",
    "          do(o, l, r)\n",
    "          return\n",
    "        m = (l + r) >> 1\n",
    "        if flip[o]:\n",
    "          do(o * 2, l, m)\n",
    "          do(o * 2 + 1, m + 1, r)\n",
    "          flip[o] = False\n",
    "        if L <= m:\n",
    "          update(o * 2, l, m, L, R)\n",
    "        if R > m:\n",
    "          update(o * 2 + 1, m + 1, r, L, R)\n",
    "        maintain(o)\n",
    "\n",
    "      build(1, 1, n)\n",
    "      s = sum(nums2)\n",
    "      ans = []\n",
    "      for op, l, r in queries:\n",
    "        if op == 1: update(1, 1, n, l + 1, r + 1)\n",
    "        elif op == 2: s += l * cnt1[1]\n",
    "        else: ans.append(s)\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        cnt1 = [0] * (4 * n)\n",
    "        #懒标记， 记录要不要往下传翻转\n",
    "        todo = [False] * (4 * n)\n",
    "\n",
    "        # 维护区间 1 的个数\n",
    "        def maintain(o: int) -> None:\n",
    "            cnt1[o] = cnt1[o * 2] + cnt1[o * 2 + 1]\n",
    "\n",
    "\n",
    "        def do(o: int, l: int, r: int) -> None:\n",
    "            cnt1[o] = r - l + 1 - cnt1[o]\n",
    "            todo[o] = not todo[o]\n",
    "\n",
    "        # 初始化线段树   o,l,r=1,1,n\n",
    "        def build(o: int, l: int, r: int) -> None:\n",
    "            if l == r:\n",
    "                cnt1[o] = nums1[l - 1]\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            build(o * 2, l, m)\n",
    "            build(o * 2 + 1, m + 1, r)\n",
    "            maintain(o)\n",
    "\n",
    "        # 更新前缀 [L,R]   o,l,r=1,1,n\n",
    "        def update(o: int, l: int, r: int, L: int, R: int) -> None:\n",
    "            if L <= l and r <= R:\n",
    "                do(o, l, r)\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            if todo[o]:\n",
    "                do(o * 2, l, m)\n",
    "                do(o * 2 + 1, m + 1, r)\n",
    "                todo[o] = False\n",
    "            if m >= L: update(o * 2, l, m, L, R)\n",
    "            if m < R: update(o * 2 + 1, m + 1, r, L, R)\n",
    "            maintain(o)\n",
    "        \n",
    "        def query(o: int, l: int, r: int, L: int, R: int) -> None:\n",
    "            if L <= l and r <= R:\n",
    "                return cnt1[o]\n",
    "            m = (l + r) // 2\n",
    "            if todo[o]:\n",
    "                do(o * 2, l, m)\n",
    "                do(o * 2 + 1, m + 1, r)\n",
    "                todo[o] = False\n",
    "            left = right = 0\n",
    "            if m >= L: left = query(o * 2, l, m, L, R)\n",
    "            if m < R: right = query(o * 2 + 1, m + 1, r, L, R)\n",
    "            return left + right\n",
    "        build(1, 1, n)\n",
    "        s = sum(nums2)\n",
    "        ans = []\n",
    "        for op, l, r in queries:\n",
    "            if op == 1: update(1, 1, n, l + 1, r + 1)\n",
    "            elif op == 2: s += l * query(1, 1, n, 1, n)\n",
    "            else: ans.append(s)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        cnt1 = [0] * (4 * n)\n",
    "        flip = [False] * (4 * n)\n",
    "\n",
    "        # 维护区间 1 的个数\n",
    "        def maintain(o: int) -> None:\n",
    "            cnt1[o] = cnt1[o * 2] + cnt1[o * 2 + 1]\n",
    "\n",
    "        # 执行区间反转\n",
    "        def do(o: int, l: int, r: int) -> None:\n",
    "            cnt1[o] = r - l + 1 - cnt1[o]\n",
    "            flip[o] = not flip[o]\n",
    "\n",
    "        # 初始化线段树   o,l,r=1,1,n\n",
    "        def build(o: int, l: int, r: int) -> None:\n",
    "            if l == r:\n",
    "                cnt1[o] = nums1[l - 1]\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            build(o * 2, l, m)\n",
    "            build(o * 2 + 1, m + 1, r)\n",
    "            maintain(o)\n",
    "\n",
    "        # 反转区间 [L,R]   o,l,r=1,1,n\n",
    "        def update(o: int, l: int, r: int, L: int, R: int) -> None:\n",
    "            if L <= l and r <= R:\n",
    "                do(o, l, r)\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            if flip[o]:\n",
    "                do(o * 2, l, m)\n",
    "                do(o * 2 + 1, m + 1, r)\n",
    "                flip[o] = False\n",
    "            if m >= L: update(o * 2, l, m, L, R)\n",
    "            if m < R: update(o * 2 + 1, m + 1, r, L, R)\n",
    "            maintain(o)\n",
    "\n",
    "        build(1, 1, n)\n",
    "        ans, s = [], sum(nums2)\n",
    "        for op, l, r in queries:\n",
    "            if op == 1: update(1, 1, n, l + 1, r + 1)\n",
    "            elif op == 2: s += l * cnt1[1]\n",
    "            else: ans.append(s)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        cnt1 = [0] * (4 * n)\n",
    "        flip = [False] * (4 * n)\n",
    "\n",
    "        # 维护区间 1 的个数\n",
    "        def maintain(o: int) -> None:\n",
    "            cnt1[o] = cnt1[o * 2] + cnt1[o * 2 + 1]\n",
    "\n",
    "        # 执行区间反转\n",
    "        def do(o: int, l: int, r: int) -> None:\n",
    "            cnt1[o] = r - l + 1 - cnt1[o]\n",
    "            flip[o] = not flip[o]\n",
    "\n",
    "        # 初始化线段树   o,l,r=1,1,n\n",
    "        def build(o: int, l: int, r: int) -> None:\n",
    "            if l == r:\n",
    "                cnt1[o] = nums1[l - 1]\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            build(o * 2, l, m)\n",
    "            build(o * 2 + 1, m + 1, r)\n",
    "            maintain(o)\n",
    "\n",
    "        # 反转区间 [L,R]   o,l,r=1,1,n\n",
    "        def update(o: int, l: int, r: int, L: int, R: int) -> None:\n",
    "            if L <= l and r <= R:\n",
    "                do(o, l, r)\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            if flip[o]:\n",
    "                do(o * 2, l, m)\n",
    "                do(o * 2 + 1, m + 1, r)\n",
    "                flip[o] = False\n",
    "            if m >= L: update(o * 2, l, m, L, R)\n",
    "            if m < R: update(o * 2 + 1, m + 1, r, L, R)\n",
    "            maintain(o)\n",
    "\n",
    "        build(1, 1, n)\n",
    "        ans, s = [], sum(nums2)\n",
    "        for op, l, r in queries:\n",
    "            if op == 1: update(1, 1, n, l + 1, r + 1)\n",
    "            elif op == 2: s += l * cnt1[1]\n",
    "            else: ans.append(s)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n=len(nums1)\n",
    "        cnt1=[0]*(4*n)\n",
    "        flip=[False]*(4*n) \n",
    "\n",
    "        def maintain(o:int)->None:\n",
    "            cnt1[o]=cnt1[o*2]+cnt1[o*2+1]\n",
    "        \n",
    "        def do(o:int,l:int,r:int)->None:\n",
    "            cnt1[o]=r-l+1-cnt1[o]\n",
    "            flip[o]=not flip[o]\n",
    "        \n",
    "        def build(o:int,l:int,r:int)->None:\n",
    "            if l==r:\n",
    "                cnt1[o]=nums1[l-1]\n",
    "                return\n",
    "            m=(l+r) // 2\n",
    "            build(o*2,l,m)\n",
    "            build(o*2+1,m+1,r)\n",
    "            maintain(o) \n",
    "\n",
    "        def update(o:int,l:int,r:int,L:int,R:int)->None:\n",
    "            if L<=l and r<=R:\n",
    "                do(o, l, r) \n",
    "                return\n",
    "\n",
    "            m=(l+r) //2 \n",
    "            if flip[o]:\n",
    "                do(o*2,l,m)  \n",
    "                do(o*2+1,m+1,r)  \n",
    "                flip[o]=False\n",
    "            if m>=L:update(o*2,l,m,L,R) \n",
    "            if m<R: update(o*2+1,m+1,r,L,R)  \n",
    "            maintain(o)  \n",
    "\n",
    "        build(1,1,n)  \n",
    "        ans,s=[],sum(nums2)\n",
    "        for op,l,r in queries:\n",
    "            if op==1 : update(1,1,n,l+1,r+1)\n",
    "            elif op==2: s+=l*cnt1[1]  #因为不是区间查询，可以不用打上lazy标记\n",
    "            else: ans.append(s)  \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 操作1：翻转给定区间[r,l]内的0，1\n",
    "        # 操作2：nums2[i] = nums2[i] + nums1[i] * p\n",
    "        # 操作3： 对nums2求和\n",
    "\n",
    "        n = len(nums1)\n",
    "        cnt1 = [0] * (4 * n)\n",
    "        flip = [False] * (4 * n)\n",
    "\n",
    "        def maintain(o: int) -> None: # 维护区间1的个数\n",
    "            cnt1[o] = cnt1[o * 2] + cnt1[o * 2 + 1]\n",
    "\n",
    "        def do(o: int, l: int, r: int) -> None: # 执行区间翻转\n",
    "            cnt1[o] = r - l + 1 - cnt1[o]\n",
    "            flip[o] = not flip[o]\n",
    "\n",
    "        # 初始化线段树   o,l,r=1,1,n\n",
    "        def build(o: int, l: int, r: int) -> None:\n",
    "            if l == r:\n",
    "                cnt1[o] = nums1[l - 1]\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            build(o * 2, l, m)\n",
    "            build(o * 2 + 1, m + 1, r)\n",
    "            maintain(o)\n",
    "\n",
    "        # 反转区间 [L,R]   o,l,r=1,1,n\n",
    "        def update(o: int, l: int, r: int, L: int, R: int) -> None:\n",
    "            if L <= l and r <= R:\n",
    "                do(o, l, r)\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            if flip[o]:\n",
    "                do(o * 2, l, m)\n",
    "                do(o * 2 + 1, m + 1, r)\n",
    "                flip[o] = False\n",
    "            if m >= L: update(o * 2, l, m, L, R)\n",
    "            if m < R: update(o * 2 + 1, m + 1, r, L, R)\n",
    "            maintain(o)\n",
    "\n",
    "        build(1, 1, n)\n",
    "        ans, s = [], sum(nums2)\n",
    "        for op, l, r in queries:\n",
    "            if op == 1: update(1, 1, n, l + 1, r + 1)\n",
    "            elif op == 2: s += l * cnt1[1]\n",
    "            else: ans.append(s)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        cnt1 = [0] * (4 * n)\n",
    "        flip = [False] * (4 * n)\n",
    "\n",
    "        # 维护区间 1 的个数\n",
    "        def maintain(o: int) -> None:\n",
    "            cnt1[o] = cnt1[o * 2] + cnt1[o * 2 + 1]\n",
    "\n",
    "        # 执行区间反转\n",
    "        def do(o: int, l: int, r: int) -> None:\n",
    "            cnt1[o] = r - l + 1 - cnt1[o]\n",
    "            flip[o] = not flip[o]\n",
    "\n",
    "        # 初始化线段树   o,l,r=1,1,n\n",
    "        def build(o: int, l: int, r: int) -> None:\n",
    "            if l == r:\n",
    "                cnt1[o] = nums1[l - 1]\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            build(o * 2, l, m)\n",
    "            build(o * 2 + 1, m + 1, r)\n",
    "            maintain(o)\n",
    "\n",
    "        # 反转区间 [L,R]   o,l,r=1,1,n\n",
    "        def update(o: int, l: int, r: int, L: int, R: int) -> None:\n",
    "            if L <= l and r <= R:\n",
    "                do(o, l, r)\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            if flip[o]:\n",
    "                do(o * 2, l, m)\n",
    "                do(o * 2 + 1, m + 1, r)\n",
    "                flip[o] = False\n",
    "            if m >= L: update(o * 2, l, m, L, R)\n",
    "            if m < R: update(o * 2 + 1, m + 1, r, L, R)\n",
    "            maintain(o)\n",
    "\n",
    "        build(1, 1, n)\n",
    "        ans, s = [], sum(nums2)\n",
    "        for op, l, r in queries:\n",
    "            if op == 1: update(1, 1, n, l + 1, r + 1)\n",
    "            elif op == 2: s += l * cnt1[1]\n",
    "            else: ans.append(s)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        cnt = [0]*(4*n)\n",
    "        todo = [False]*(4*n)\n",
    "\n",
    "        # 求非叶子节点\n",
    "        def maintain(o):\n",
    "            cnt[o] = cnt[o*2] + cnt[o*2+1]\n",
    "        # 进行01翻转\n",
    "        def do(o, l, r):\n",
    "            # 翻转\n",
    "            cnt[o] = r-l+1-cnt[o]\n",
    "            # 翻一次为反，翻两次为正\n",
    "            todo[o] = not todo[o]\n",
    "\n",
    "        # 初始化线段树\n",
    "        def build(o, l, r):\n",
    "            # 叶子结点\n",
    "            if l == r:\n",
    "                cnt[o] = nums1[l-1]\n",
    "                return\n",
    "            # 非叶子结点 \n",
    "            mid = (l+r)//2\n",
    "            build(o*2, l, mid)\n",
    "            build(o*2+1, mid+1, r)\n",
    "            maintain(o)\n",
    "        \n",
    "        def update(o, l, r, L, R):\n",
    "            if L<=l and r<=R:\n",
    "                do(o, l, r)\n",
    "                return\n",
    "            mid = (l+r)//2\n",
    "            # 先将当前节点的值传给子节点\n",
    "            if todo[o]:\n",
    "                do(o*2, l, mid)\n",
    "                do(o*2+1, mid+1, r)\n",
    "                todo[o]=False\n",
    "            \n",
    "            if mid>=L:\n",
    "                update(o*2, l, mid, L, R)\n",
    "            if mid<R:\n",
    "                update(o*2+1,mid+1, r, L, R)\n",
    "            maintain(o)\n",
    "        \n",
    "        build(1, 1, n)\n",
    "        ans, s = [], sum(nums2)\n",
    "        for op, l, r in queries:\n",
    "            if op == 1:\n",
    "                update(1, 1, n, l+1, r+1)\n",
    "            elif op == 2:\n",
    "                s += l*cnt[1]\n",
    "            else:\n",
    "                ans.append(s)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        #更新一个子数组的值，把子数组内的元素取反\n",
    "        # 查询一个子数组的值，求和\n",
    "        # lazy更新，延迟更新\n",
    "        #lazy_tag: 用一个数组维护每个区间需要更新的值。\n",
    "        n=len(nums1)\n",
    "        todo=[False]*4*n\n",
    "        cnt1=[0]*4*n\n",
    "        def maintain(o):\n",
    "            cnt1[o]=cnt1[o*2]+cnt1[o*2+1]\n",
    "            return\n",
    "\n",
    "\n",
    "        def build(o,l,r):\n",
    "            if l==r:\n",
    "                cnt1[o]=nums1[l-1]\n",
    "                return\n",
    "\n",
    "            m=(l+r)//2\n",
    "            build(o*2,l,m)\n",
    "            build(o*2+1,m+1,r)\n",
    "            maintain(o)\n",
    "\n",
    "        def do(o,l,r): # 执行区间反转\n",
    "            cnt1[o]=r-l+1-cnt1[o]\n",
    "            todo[o]=not todo[o]\n",
    "\n",
    "\n",
    "        def update(o,l,r,L,R): #翻转区间[L，R]\n",
    "            if L<=l and R>=r:\n",
    "                do(o,l,r)\n",
    "                return\n",
    "            m=(l+r)//2\n",
    "            if todo[o]:\n",
    "                do(o*2,l,m)\n",
    "                do(o*2+1,m+1,r)\n",
    "                todo[o]=False\n",
    "\n",
    "            if m>=L:\n",
    "                update(o*2,l,m,L,R)\n",
    "            if m+1<=R:\n",
    "                update(o*2+1,m+1,r,L,R)\n",
    "            maintain(o)\n",
    "                #维护\n",
    "        build(1,1,n)\n",
    "        ans=[]\n",
    "        s=sum(nums2)\n",
    "        for op,l,r in queries:\n",
    "            if op==1: update(1,1,n,l+1,r+1)\n",
    "            elif op==2: s+=l*cnt1[1]\n",
    "            else: ans.append(s)\n",
    "        return ans \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1, nums2, queries):\n",
    "        S=SegmentTree(nums1)\n",
    "        S2=sum(nums2)\n",
    "        ans=[]\n",
    "        for q in queries:\n",
    "            if q[0]==1:\n",
    "                S.update(q[1],q[2]+1)\n",
    "            elif q[0]==2:\n",
    "                S2+=q[1]*S.find(0,len(nums1))\n",
    "            else:\n",
    "                ans.append(S2)\n",
    "        return ans\n",
    "            \n",
    "\n",
    "class SegmentTree():\n",
    "    def __init__(self,nums) -> None:\n",
    "        self.nums=nums\n",
    "        self.Tree=[0]*4*len(nums)\n",
    "        self.N=len(nums)\n",
    "        self.lazy=[0]*4*len(nums)\n",
    "        self.BuildTree()\n",
    "    def BuildTree(self):\n",
    "        def build(left,right,n):\n",
    "            if left+1==right:\n",
    "                self.Tree[n]=self.nums[left]\n",
    "                return\n",
    "            elif left<right-1:\n",
    "                mid=(left+right)//2\n",
    "                build(left,mid,2*n+1)\n",
    "                build(mid,right,2*n+2)\n",
    "                self.Tree[n]=self.Tree[2*n+1]+self.Tree[2*n+2]\n",
    "            return\n",
    "        build(0,len(self.nums),0)\n",
    "    def update(self,i,j):\n",
    "        def selfupdate(left,right,i,j,n):\n",
    "            if i==left and right==j:\n",
    "                self.lazy[n]=1-self.lazy[n]\n",
    "                self.Tree[n]=right-left-self.Tree[n]\n",
    "                return\n",
    "            mid=(left+right)//2\n",
    "            if self.lazy[n]>0:\n",
    "                self.lazy[2*n+1]=1-self.lazy[2*n+1]\n",
    "                self.Tree[2*n+1]=mid-left-self.Tree[2*n+1]\n",
    "                self.lazy[2*n+2]=1-self.lazy[2*n+2]\n",
    "                self.Tree[2*n+2]=right-mid-self.Tree[2*n+2]\n",
    "                self.lazy[n]=0\n",
    "            if mid>=j:\n",
    "                selfupdate(left,mid,i,j,2*n+1)\n",
    "            elif mid<=i:\n",
    "                selfupdate(mid,right,i,j,2*n+2)\n",
    "            else:\n",
    "                selfupdate(left,mid,i,mid,2*n+1)\n",
    "                selfupdate(mid,right,mid,j,2*n+2)\n",
    "            self.Tree[n]=self.Tree[2*n+1]+self.Tree[2*n+2]\n",
    "            return\n",
    "        selfupdate(0,len(self.nums),i,j,0)\n",
    "    def find(self,i,j):\n",
    "        def selffind(left,right,i,j,n):\n",
    "            if i==left and right==j:\n",
    "                return self.Tree[n]\n",
    "            mid=(left+right)//2\n",
    "            if self.lazy[n]>0:\n",
    "                self.lazy[2*n+1]=1-self.lazy[2*n+1]\n",
    "                self.Tree[2*n+1]=mid-left-self.Tree[2*n+1]\n",
    "                self.lazy[2*n+2]=1-self.lazy[2*n+2]\n",
    "                self.Tree[2*n+2]=right-mid-self.Tree[2*n+2]\n",
    "                self.lazy[n]=0\n",
    "            if mid>=j:\n",
    "                return selffind(left,mid,i,j,2*n+1)\n",
    "            elif mid<=i:\n",
    "                return selffind(mid,right,i,j,2*n+2)\n",
    "            else:\n",
    "                return selffind(left,mid,i,mid,2*n+1)+selffind(mid,right,mid,j,2*n+2)\n",
    "        return selffind(0,len(self.nums),i,j,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        cnt1 = [0] * (4 * n)\n",
    "        flip = [False] * (4 * n)\n",
    "\n",
    "        # 维护区间 1 的个数\n",
    "        def maintain(o: int) -> None:\n",
    "            cnt1[o] = cnt1[o * 2] + cnt1[o * 2 + 1]\n",
    "\n",
    "        # 执行区间反转\n",
    "        def do(o: int, l: int, r: int) -> None:\n",
    "            cnt1[o] = r - l + 1 - cnt1[o]\n",
    "            flip[o] = not flip[o]\n",
    "\n",
    "        def build(o: int, l: int, r: int) ->None:\n",
    "            if l == r:\n",
    "                cnt1[o] = nums1[l - 1]\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            build(o * 2, l, m)\n",
    "            build(o * 2 + 1, m + 1, r)\n",
    "            maintain(o)\n",
    "\n",
    "        def update(o: int, l: int, r: int, L: int, R: int) -> None:\n",
    "            if L <= l and r <= R:\n",
    "                do(o, l, r)\n",
    "                return \n",
    "            m = (l + r) // 2\n",
    "            if flip[o]:\n",
    "                do(o * 2, l, m)\n",
    "                do(o * 2 + 1, m + 1, r)\n",
    "                flip[o] = False\n",
    "       \n",
    "            if m >= L: update(2 * o, l, m, L, R)\n",
    "            if m <R : update(2 * o + 1, m + 1, r, L, R)\n",
    "            maintain(o)\n",
    "        build(1,1,n)\n",
    "        ans, s = [], sum(nums2)\n",
    "        for op, l, r in queries:\n",
    "            if op == 1: update(1, 1, n, l + 1, r + 1)\n",
    "            elif op == 2: s += l * cnt1[1]\n",
    "            else: ans.append(s)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        cut = [0]*4*n\n",
    "        lazy = [False]*4*n\n",
    "        #用来计算自己区间的维护的1的值\n",
    "        def maintain(index):\n",
    "            cut[index] = cut[index*2]+cut[index*2+1]\n",
    "        #用来建树\n",
    "        def build(index,l,r):\n",
    "            #index用来表示线段树的数组\n",
    "            #l,r用来表示nums1的区间\n",
    "            if l == r:\n",
    "                cut[index] = nums1[l-1]\n",
    "                return \n",
    "            mid = (l+r)//2\n",
    "            build(index*2,l,mid)\n",
    "            build(index*2+1,mid+1,r)\n",
    "            maintain(index)\n",
    "        #执行区间反转 相当于更新操作\n",
    "        def rev(index,l,r):\n",
    "            cut[index] = r-l+1-cut[index]\n",
    "            lazy[index] = not lazy[index]\n",
    "        def update(index,l,r,L,R):\n",
    "            if l>=L and r<=R:\n",
    "                rev(index,l,r)\n",
    "                return\n",
    "            mid = (l+r)//2\n",
    "            #当lazy时，需要向下传\n",
    "            if lazy[index]:\n",
    "                rev(index*2,l,mid)\n",
    "                rev(index*2+1,mid+1,r)\n",
    "                lazy[index] = False\n",
    "            if L<=mid:\n",
    "                update(index*2,l,mid,L,R)\n",
    "            if mid+1<=R:\n",
    "                update(index*2+1,mid+1,r,L,R)\n",
    "            maintain(index)\n",
    "        \n",
    "        build(1,1,n)\n",
    "        ans, s = [], sum(nums2)\n",
    "        for i,j,k in queries:\n",
    "            if i == 1:\n",
    "                update(1,1,n,j+1,k+1)\n",
    "            elif i == 2:s+=j*cut[1]\n",
    "            else:ans.append(s)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        n2Sum = sum(nums2)\n",
    "        st = [0] * (4 * n + 1)\n",
    "        lazy = [False] * (4 * n + 1)\n",
    "        \n",
    "        def reversed(node, left, right):\n",
    "            st[node] = (right - left + 1) - st[node]\n",
    "\n",
    "        def build(node = 1, left = 0, right = n - 1):\n",
    "            if left == right:\n",
    "                st[node] = nums1[left]\n",
    "                return\n",
    "            mid = left + right >> 1\n",
    "            build(node * 2, left, mid)\n",
    "            build(node * 2 + 1, mid + 1, right)\n",
    "            st[node] = st[node * 2] + st[node * 2 + 1]\n",
    "        \n",
    "        def update(L, R, node = 1, left = 0, right = n - 1):\n",
    "            if left > R or right < L: return\n",
    "            if left >= L and right <= R:\n",
    "                reversed(node, left, right)\n",
    "                if left != right:\n",
    "                    lazy[node] = not lazy[node]\n",
    "                return \n",
    "            \n",
    "            mid = left + right >> 1\n",
    "\n",
    "            if lazy[node]:\n",
    "                reversed(node * 2, left, mid)\n",
    "                reversed(node * 2 + 1, mid + 1, right)\n",
    "                lazy[node * 2] = not lazy[node * 2]\n",
    "                lazy[node * 2 + 1] = not lazy[node * 2 + 1]\n",
    "                lazy[node] = False\n",
    "\n",
    "            update(L, R, node * 2, left, mid)\n",
    "            update(L, R, node * 2 + 1, mid + 1, right)\n",
    "            st[node] = st[node * 2] + st[node * 2 + 1]\n",
    "\n",
    "        build()\n",
    "        res = []\n",
    "        for t, l, r in queries:\n",
    "            if t == 2: n2Sum += st[1] * l\n",
    "            elif t == 3: res.append(n2Sum)\n",
    "            else: update(l, r)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # Lazy 线段树\n",
    "    # https://leetcode.cn/problems/handling-sum-queries-after-update/solutions/2119436/xian-duan-shu-by-endlesscheng-vx80/\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        cnt1 = [0] * (4 * n)\n",
    "        flip = [False] * (4 * n)\n",
    "\n",
    "        # 维护区间 1 的个数\n",
    "        def maintain(o: int) -> None:\n",
    "            cnt1[o] = cnt1[o * 2] + cnt1[o * 2 + 1]\n",
    "\n",
    "\n",
    "        # 执行区间反转\n",
    "        def do(o: int, l: int, r: int) -> None:\n",
    "            cnt1[o] = r - l + 1 - cnt1[o]\n",
    "            flip[o] = not flip[o]\n",
    "\n",
    "\n",
    "        # 初始化线段树   o,l,r=1,1,n\n",
    "        def build(o: int, l: int, r: int) -> None:\n",
    "            if l == r:\n",
    "                cnt1[o] = nums1[l - 1]\n",
    "                return\n",
    "\n",
    "            m = (l + r) // 2\n",
    "            build(o * 2, l, m)\n",
    "            build(o * 2 + 1, m + 1, r)\n",
    "            maintain(o)\n",
    "\n",
    "\n",
    "        # 反转区间 [L,R]   o,l,r=1,1,n\n",
    "        def update(o: int, l: int, r: int, L: int, R: int) -> None:\n",
    "            if L <= l and r <= R:\n",
    "                do(o, l, r)\n",
    "                return\n",
    "                \n",
    "            m = (l + r) // 2\n",
    "            if flip[o]:\n",
    "                do(o * 2, l, m)\n",
    "                do(o * 2 + 1, m + 1, r)\n",
    "                flip[o] = False\n",
    "\n",
    "            if m >= L:\n",
    "                update(o * 2, l, m, L, R)\n",
    "\n",
    "            if m < R:\n",
    "                update(o * 2 + 1, m + 1, r, L, R)\n",
    "\n",
    "            maintain(o)\n",
    "\n",
    "\n",
    "        build(1, 1, n)\n",
    "        ans, s = [], sum(nums2)\n",
    "        for op, l, r in queries:\n",
    "            if op == 1:\n",
    "                update(1, 1, n, l + 1, r + 1)\n",
    "            elif op == 2:\n",
    "                s += l * cnt1[1]\n",
    "            else:\n",
    "                ans.append(s)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        #更新一个子数组的值，把子数组内的元素取反\n",
    "        # 查询一个子数组的值，求和\n",
    "        # lazy更新，延迟更新\n",
    "        #lazy_tag: 用一个数组维护每个区间需要更新的值。\n",
    "        n=len(nums1)\n",
    "        todo=[False]*4*n\n",
    "        cnt1=[0]*4*n\n",
    "        def maintain(o):\n",
    "            cnt1[o]=cnt1[o*2]+cnt1[o*2+1]\n",
    "            return\n",
    "\n",
    "\n",
    "        def build(o,l,r):\n",
    "            if l==r:\n",
    "                cnt1[o]=nums1[l-1]\n",
    "                return\n",
    "\n",
    "            m=(l+r)//2\n",
    "            build(o*2,l,m)\n",
    "            build(o*2+1,m+1,r)\n",
    "            maintain(o)\n",
    "\n",
    "        def do(o,l,r): # 执行区间反转\n",
    "            cnt1[o]=r-l+1-cnt1[o]\n",
    "            todo[o]=not todo[o]\n",
    "\n",
    "\n",
    "        def update(o,l,r,L,R): #翻转区间[L，R]\n",
    "            if L<=l and R>=r:\n",
    "                do(o,l,r)\n",
    "                return\n",
    "            m=(l+r)//2\n",
    "            if todo[o]:\n",
    "                do(o*2,l,m)\n",
    "                do(o*2+1,m+1,r)\n",
    "                todo[o]=False\n",
    "\n",
    "            if m>=L:\n",
    "                update(o*2,l,m,L,R)\n",
    "            if m+1<=R:\n",
    "                update(o*2+1,m+1,r,L,R)\n",
    "            maintain(o)\n",
    "                #维护\n",
    "        build(1,1,n)\n",
    "        ans=[]\n",
    "        s=sum(nums2)\n",
    "        for op,l,r in queries:\n",
    "            if op==1: update(1,1,n,l+1,r+1)\n",
    "            elif op==2: s+=l*cnt1[1]\n",
    "            else: ans.append(s)\n",
    "        return ans \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        cnt = [0] * (n * 4)\n",
    "        todo = [False] * (n * 4)\n",
    "\n",
    "        # 维护区间内1的个数\n",
    "        def maintain(o):\n",
    "            cnt[o] = cnt[o * 2] + cnt[o * 2 + 1]\n",
    "\n",
    "        # 对区间进行翻转操作\n",
    "        def do(o, l, r):\n",
    "            cnt[o] = r - l + 1 - cnt[o]\n",
    "            todo[o] = not todo[o]\n",
    "\n",
    "        # 构建线段树，O(n)\n",
    "        def build(o, l ,r):\n",
    "            if l == r:\n",
    "                cnt[o] = nums1[l-1]\n",
    "                return \n",
    "            m = (l + r) // 2\n",
    "            build(o * 2, l, m)\n",
    "            build(o * 2 + 1, m + 1, r)\n",
    "            maintain(o)\n",
    "        \n",
    "        # 更新线段树，O(log n)\n",
    "        def update(o, l, r, L, R):\n",
    "            # 如果区间被[L, R]完全包含，直接标记当前区间（可重复标记）\n",
    "            if L <= l and r <= R:\n",
    "                do(o, l, r)\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            # 如果该区间已经被lazy tag标记过，而且区间未被[L, R]完全包含，\n",
    "            # 那么需要将标记传递给左右儿子节点，并取消该节点的标记\n",
    "            if todo[o]:\n",
    "                do(o * 2, l, m)\n",
    "                do(o * 2 + 1,m + 1, r)\n",
    "                todo[o] = False\n",
    "            \n",
    "            # 更新左右子节点\n",
    "            if m >= L:\n",
    "                update(o * 2, l, m, L, R)\n",
    "            if m < R:\n",
    "                update(o * 2 + 1, m + 1, r, L, R)\n",
    "\n",
    "            # 维护当前节点的cnt\n",
    "            maintain(o)\n",
    "        \n",
    "        build(1, 1, n)\n",
    "        sm = sum(nums2)\n",
    "        ans = []\n",
    "        for op, l, r in queries:\n",
    "            if op == 1:\n",
    "                update(1, 1, n, l + 1, r + 1)\n",
    "            elif op == 2:\n",
    "                sm += cnt[1] * l\n",
    "            else:\n",
    "                ans.append(sm)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        #更新一个子数组的值，把子数组内的元素取反\n",
    "        # 查询一个子数组的值，求和\n",
    "        # lazy更新，延迟更新\n",
    "        #lazy_tag: 用一个数组维护每个区间需要更新的值。\n",
    "        n=len(nums1)\n",
    "        todo=[False]*4*n\n",
    "        cnt1=[0]*4*n\n",
    "        def maintain(o):\n",
    "            cnt1[o]=cnt1[o*2]+cnt1[o*2+1]\n",
    "            return\n",
    "\n",
    "\n",
    "        def build(o,l,r):\n",
    "            if l==r:\n",
    "                cnt1[o]=nums1[l-1]\n",
    "                return\n",
    "\n",
    "            m=(l+r)//2\n",
    "            build(o*2,l,m)\n",
    "            build(o*2+1,m+1,r)\n",
    "            maintain(o)\n",
    "\n",
    "        def do(o,l,r): # 执行区间反转\n",
    "            cnt1[o]=r-l+1-cnt1[o]\n",
    "            todo[o]=not todo[o]\n",
    "\n",
    "\n",
    "        def update(o,l,r,L,R): #翻转区间[L，R]\n",
    "            if L<=l and R>=r:\n",
    "                do(o,l,r)\n",
    "                return\n",
    "            m=(l+r)//2\n",
    "            if todo[o]:\n",
    "                do(o*2,l,m)\n",
    "                do(o*2+1,m+1,r)\n",
    "                todo[o]=False\n",
    "\n",
    "            if m>=L:\n",
    "                update(o*2,l,m,L,R)\n",
    "            if m+1<=R:\n",
    "                update(o*2+1,m+1,r,L,R)\n",
    "            maintain(o)\n",
    "                #维护\n",
    "        build(1,1,n)\n",
    "        ans=[]\n",
    "        s=sum(nums2)\n",
    "        for op,l,r in queries:\n",
    "            if op==1: update(1,1,n,l+1,r+1)\n",
    "            elif op==2: s+=l*cnt1[1]\n",
    "            else: ans.append(s)\n",
    "        return ans \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n=len(nums1)\n",
    "        cnt1= [0] * (4*n)\n",
    "        flip=[False] * (4*n)\n",
    "\n",
    "        def maintain(o:int):\n",
    "            cnt1[o]=cnt1[o*2]+cnt1[o*2+1]\n",
    "        \n",
    "        def do(o:int, l:int ,r:int):\n",
    "            cnt1[o]=r-l+1-cnt1[o]\n",
    "            flip[o]=not flip[o]\n",
    "        \n",
    "        def build(o:int ,l:int,r:int):\n",
    "            if l==r:\n",
    "                cnt1[o]=nums1[l-1]\n",
    "                return\n",
    "            m=(l+r)//2\n",
    "            build(o*2,l,m)\n",
    "            build(o*2+1,m+1,r)\n",
    "            maintain(o)\n",
    "\n",
    "        def update(o:int,l:int,r:int,L:int,R:int):\n",
    "            if L<=l and r<=R:\n",
    "                do(o,l,r)\n",
    "                return\n",
    "            m=(l+r)//2\n",
    "            if flip[o]:\n",
    "                do(o*2,l,m)\n",
    "                do(o*2+1,m+1,r)\n",
    "                flip[o]=False\n",
    "            if m>=L: update(o*2,l,m,L,R)\n",
    "            if m<R: update(o*2+1,m+1,r,L,R)\n",
    "            maintain(o)\n",
    "        \n",
    "        build(1,1,n)\n",
    "        ans,s=[],sum(nums2)\n",
    "        for op,l,r in queries:\n",
    "            if op ==1 : update(1,1,n,l+1,r+1)\n",
    "            elif op==2: s+=l*cnt1[1]\n",
    "            else: ans.append(s)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        def maintain(i: int) -> None:\n",
    "            # 更新线段树 i 点的值\n",
    "            nums1_segmen_tree[i] = nums1_segmen_tree[2 * i] + nums1_segmen_tree[2 * i + 1]\n",
    "\n",
    "        def build(i: int, l: int, r: int) -> None:\n",
    "            ''' build a segment tree\n",
    "            '''\n",
    "            if l == r:\n",
    "                nums1_segmen_tree[i] = nums1[l - 1]\n",
    "                return\n",
    "            m = l + (r - l) // 2\n",
    "            build(i * 2, l, m)\n",
    "            build(i * 2 + 1, m + 1, r)\n",
    "            maintain(i)\n",
    "\n",
    "        def set_lazy(i: int, l: int, r: int) -> None:\n",
    "            nums1_segmen_tree[i] = r - l + 1 - nums1_segmen_tree[i]\n",
    "            lazy[i] = not lazy[i]\n",
    "        \n",
    "        def update(i: int, l: int, r: int, L: int, R: int) -> None:\n",
    "            ''' 区间更新线段树的值\n",
    "            '''\n",
    "            if L <= l and R >= r:\n",
    "                set_lazy(i, l, r)\n",
    "                return\n",
    "            m = l + (r - l) // 2\n",
    "            if lazy[i]:\n",
    "                set_lazy(2 * i, l, m)\n",
    "                set_lazy(2 * i + 1, m + 1, r)\n",
    "                lazy[i] = not lazy[i]\n",
    "            if L <= m:\n",
    "                update(i * 2, l, m, L, R)\n",
    "            if R > m:\n",
    "                update(i * 2 + 1, m + 1, r, L, R)\n",
    "            maintain(i)\n",
    "\n",
    "        def qurey(i: int, l: int, r: int, L: int, R: int) -> int:\n",
    "            ''' 查询线段树区间，考虑lazy标记\n",
    "            '''\n",
    "            if L <= l and R >= r:\n",
    "                return nums1_segmen_tree[i]\n",
    "            m = l + (r - l) // 2\n",
    "            if lazy[i]:\n",
    "                set_lazy(2 * i, l, m)\n",
    "                set_lazy(2 * i + 1, m + 1, r)\n",
    "                lazy[i] = not lazy[i]\n",
    "            res = 0\n",
    "            if L <= m:\n",
    "                res += qurey(2 * i, l, m, L, R)\n",
    "            if R > m:\n",
    "                res += qurey(2 * i + 1, m + 1, r, L, R)\n",
    "            return res\n",
    "\n",
    "        n = len(nums1)\n",
    "        nums1_segmen_tree = [0] * (4 * n)\n",
    "        lazy = [False] * (4 * n)\n",
    "        build(1, 1, n)\n",
    "        ans = []\n",
    "        nums2_sum = sum(nums2)\n",
    "        for x, y, z in queries:\n",
    "            if x == 1:\n",
    "                update(1, 1, n, y + 1, z + 1)\n",
    "            elif x == 2:\n",
    "                nums2_sum += qurey(1, 1, n, 1, n) * y\n",
    "            else:\n",
    "                ans.append(nums2_sum)\n",
    "        return ans\n",
    "        \n",
    "                \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        blockSize = int(math.sqrt(n)) + 1\n",
    "        blockNum = math.ceil(n / blockSize)\n",
    "        blocks = []\n",
    "        d = {}\n",
    "        e = [False] * blockNum\n",
    "        f = [0] * blockNum\n",
    "        g = 0\n",
    "        h = sum(nums2)\n",
    "        for i in range(blockNum):\n",
    "            blocks.append([])\n",
    "            for j in range(blockSize):\n",
    "                if i * blockSize + j >= n:\n",
    "                    break\n",
    "                blocks[i].append(nums1[i * blockSize + j])\n",
    "                f[i] += nums1[i * blockSize + j]\n",
    "                d[i * blockSize + j] = i\n",
    "        print(blocks, d, f)\n",
    "        res = []\n",
    "        for a, b, c in queries:\n",
    "            if a == 1:\n",
    "                u, v = d[b], d[c]\n",
    "                if u == v:\n",
    "                    m = len(blocks[u])\n",
    "                    if e[u]:\n",
    "                        self.cast(blocks[u])\n",
    "                        e[u] = False\n",
    "                        f[u] = m - f[u]\n",
    "                    for i in range(m):\n",
    "                        if u * blockSize + i >= b and u * blockSize + i <= c:\n",
    "                            blocks[u][i] = 1 - blocks[u][i]\n",
    "                            if blocks[u][i] == 1:\n",
    "                                f[u] += 1\n",
    "                            else:\n",
    "                                f[u] -= 1\n",
    "                elif u + 1 == v:\n",
    "                    m = len(blocks[u])\n",
    "                    if e[u]:\n",
    "                        self.cast(blocks[u])\n",
    "                        e[u] = False\n",
    "                        f[u] = m - f[u]\n",
    "                    for i in range(m):\n",
    "                        if u * blockSize + i >= b and u * blockSize + i <= c:\n",
    "                            blocks[u][i] = 1 - blocks[u][i]\n",
    "                            if blocks[u][i] == 1:\n",
    "                                f[u] += 1\n",
    "                            else:\n",
    "                                f[u] -= 1\n",
    "\n",
    "                    m = len(blocks[v])\n",
    "                    if e[v]:\n",
    "                        self.cast(blocks[v])\n",
    "                        e[v] = False\n",
    "                        f[v] = m - f[v]\n",
    "                    for i in range(m):\n",
    "                        if v * blockSize + i >= b and v * blockSize + i <= c:\n",
    "                            blocks[v][i] = 1 - blocks[v][i]\n",
    "                            if blocks[v][i] == 1:\n",
    "                                f[v] += 1\n",
    "                            else:\n",
    "                                f[v] -= 1\n",
    "                else:\n",
    "                    for i in range(u + 1, v):\n",
    "                        e[i] = not e[i]\n",
    "                    m = len(blocks[u])\n",
    "                    if e[u]:\n",
    "                        self.cast(blocks[u])\n",
    "                        e[u] = False\n",
    "                        f[u] = m - f[u]\n",
    "                    for i in range(m):\n",
    "                        if u * blockSize + i >= b and u * blockSize + i <= c:\n",
    "                            blocks[u][i] = 1 - blocks[u][i]\n",
    "                            if blocks[u][i] == 1:\n",
    "                                f[u] += 1\n",
    "                            else:\n",
    "                                f[u] -= 1\n",
    "\n",
    "                    m = len(blocks[v])\n",
    "                    if e[v]:\n",
    "                        self.cast(blocks[v])\n",
    "                        e[v] = False\n",
    "                        f[v] = m - f[v]\n",
    "                    for i in range(m):\n",
    "                        if v * blockSize + i >= b and v * blockSize + i <= c:\n",
    "                            blocks[v][i] = 1 - blocks[v][i]\n",
    "                            if blocks[v][i] == 1:\n",
    "                                f[v] += 1\n",
    "                            else:\n",
    "                                f[v] -= 1\n",
    "            elif a == 2: \n",
    "                t = 0\n",
    "                for i in range(blockNum):\n",
    "                    if e[i] == True:\n",
    "                        t += len(blocks[i]) - f[i]\n",
    "                    else:\n",
    "                        t += f[i]\n",
    "                g += t * b\n",
    "            elif a == 3: \n",
    "                res.append(h + g)\n",
    "        return res\n",
    "\n",
    "    def cast(self, block):\n",
    "        m = len(block)\n",
    "        for i in range(m):\n",
    "            block[i] = 1 - block[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        blockSize = int(math.sqrt(n)) + 1\n",
    "        blockNum = math.ceil(n / blockSize)\n",
    "        blocks = []\n",
    "        d = {}\n",
    "        e = [False] * blockNum\n",
    "        f = [0] * blockNum\n",
    "        g = 0\n",
    "        h = sum(nums2)\n",
    "        for i in range(blockNum):\n",
    "            blocks.append([])\n",
    "            for j in range(blockSize):\n",
    "                if i * blockSize + j >= n:\n",
    "                    break\n",
    "                blocks[i].append(nums1[i * blockSize + j])\n",
    "                f[i] += nums1[i * blockSize + j]\n",
    "                d[i * blockSize + j] = i\n",
    "        res = []\n",
    "        for a, b, c in queries:\n",
    "            if a == 1:\n",
    "                u, v = d[b], d[c]\n",
    "                if u == v:\n",
    "                    m = len(blocks[u])\n",
    "                    if e[u]:\n",
    "                        self.cast(blocks[u])\n",
    "                        e[u] = False\n",
    "                        f[u] = m - f[u]\n",
    "                    for i in range(m):\n",
    "                        if u * blockSize + i >= b and u * blockSize + i <= c:\n",
    "                            blocks[u][i] = 1 - blocks[u][i]\n",
    "                            if blocks[u][i] == 1:\n",
    "                                f[u] += 1\n",
    "                            else:\n",
    "                                f[u] -= 1\n",
    "                elif u + 1 == v:\n",
    "                    m = len(blocks[u])\n",
    "                    if e[u]:\n",
    "                        self.cast(blocks[u])\n",
    "                        e[u] = False\n",
    "                        f[u] = m - f[u]\n",
    "                    for i in range(m):\n",
    "                        if u * blockSize + i >= b and u * blockSize + i <= c:\n",
    "                            blocks[u][i] = 1 - blocks[u][i]\n",
    "                            if blocks[u][i] == 1:\n",
    "                                f[u] += 1\n",
    "                            else:\n",
    "                                f[u] -= 1\n",
    "\n",
    "                    m = len(blocks[v])\n",
    "                    if e[v]:\n",
    "                        self.cast(blocks[v])\n",
    "                        e[v] = False\n",
    "                        f[v] = m - f[v]\n",
    "                    for i in range(m):\n",
    "                        if v * blockSize + i >= b and v * blockSize + i <= c:\n",
    "                            blocks[v][i] = 1 - blocks[v][i]\n",
    "                            if blocks[v][i] == 1:\n",
    "                                f[v] += 1\n",
    "                            else:\n",
    "                                f[v] -= 1\n",
    "                else:\n",
    "                    for i in range(u + 1, v):\n",
    "                        e[i] = not e[i]\n",
    "                    m = len(blocks[u])\n",
    "                    if e[u]:\n",
    "                        self.cast(blocks[u])\n",
    "                        e[u] = False\n",
    "                        f[u] = m - f[u]\n",
    "                    for i in range(m):\n",
    "                        if u * blockSize + i >= b and u * blockSize + i <= c:\n",
    "                            blocks[u][i] = 1 - blocks[u][i]\n",
    "                            if blocks[u][i] == 1:\n",
    "                                f[u] += 1\n",
    "                            else:\n",
    "                                f[u] -= 1\n",
    "\n",
    "                    m = len(blocks[v])\n",
    "                    if e[v]:\n",
    "                        self.cast(blocks[v])\n",
    "                        e[v] = False\n",
    "                        f[v] = m - f[v]\n",
    "                    for i in range(m):\n",
    "                        if v * blockSize + i >= b and v * blockSize + i <= c:\n",
    "                            blocks[v][i] = 1 - blocks[v][i]\n",
    "                            if blocks[v][i] == 1:\n",
    "                                f[v] += 1\n",
    "                            else:\n",
    "                                f[v] -= 1\n",
    "            elif a == 2: \n",
    "                t = 0\n",
    "                for i in range(blockNum):\n",
    "                    if e[i] == True:\n",
    "                        t += len(blocks[i]) - f[i]\n",
    "                    else:\n",
    "                        t += f[i]\n",
    "                g += t * b\n",
    "            elif a == 3: \n",
    "                res.append(h + g)\n",
    "        return res\n",
    "\n",
    "    def cast(self, block):\n",
    "        m = len(block)\n",
    "        for i in range(m):\n",
    "            block[i] = 1 - block[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        m1, m2 = np.array(nums1), np.array(nums2)\n",
    "        res = []\n",
    "        for o, l, r in queries:\n",
    "            if o==1: m1[l: r+1] ^= 1\n",
    "            if o==2: m2 += m1*l\n",
    "            if o==3: res.append(int(m2.sum()))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "  def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "    n = len(nums1)\n",
    "    cur = sum(nums2)\n",
    "    st = SegmentTree()\n",
    "    range_min, range_max = 0, n - 1\n",
    "    i = 0\n",
    "    while i < n:\n",
    "      if nums1[i] == 0:\n",
    "        i += 1\n",
    "        continue\n",
    "      start = i\n",
    "      i += 1\n",
    "      while i < n and nums1[i] == 1:\n",
    "        i += 1\n",
    "      st.update(st.root, range_min, range_max, start, i - 1)\n",
    "    ans = []\n",
    "    for x, y, z in queries:\n",
    "      if x == 1:\n",
    "        st.update(st.root, range_min, range_max, y, z)\n",
    "      elif x == 2:\n",
    "        cur += y * st.root.val\n",
    "      else:\n",
    "        ans.append(cur)\n",
    "    return ans\n",
    "\n",
    "class SegmentTreeNode:\n",
    "  def __init__(self) -> None:\n",
    "    self.left = self.right = None\n",
    "    self.val = self.tag = 0\n",
    "\n",
    "class SegmentTree:\n",
    " \n",
    "  def __init__(self) -> None:\n",
    "    self.root = SegmentTreeNode()\n",
    "  \n",
    "  def update(self, node, cl, cr, l, r):\n",
    "    if cl >= l and cr <= r:\n",
    "      node.val = cr - cl + 1 - node.val\n",
    "      node.tag ^= 1\n",
    "      return\n",
    "    self.pushDown(node, cl, cr)\n",
    "    mid = cl + (cr - cl) // 2\n",
    "    if mid >= l:\n",
    "      self.update(node.left, cl, mid, l, r)\n",
    "    if mid < r:\n",
    "      self.update(node.right, mid + 1, cr, l, r)\n",
    "    self.pushUp(node)\n",
    "  \n",
    "  def pushDown(self, node, cl, cr):\n",
    "    if not node.left: node.left = SegmentTreeNode()\n",
    "    if not node.right: node.right = SegmentTreeNode()\n",
    "    if not node.tag: return\n",
    "    mid = cl + (cr - cl) // 2\n",
    "    node.left.val = mid - cl + 1 - node.left.val\n",
    "    node.left.tag ^= 1\n",
    "    node.right.val = cr - mid - node.right.val\n",
    "    node.right.tag ^= 1\n",
    "    node.tag = 0\n",
    "\n",
    "  def pushUp(self, node):\n",
    "    node.val = node.left.val + node.right.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slots__ = \"l\", \"r\", \"mid\", \"leng\", \"val\", \"lazy\", \"left\", \"right\"\n",
    "\n",
    "    def __init__(self, l, r):\n",
    "        self.l = l\n",
    "        self.r = r\n",
    "        self.mid = (l + r) >> 1\n",
    "        self.leng = r - l + 1\n",
    "        # 是否翻转,0是不翻转,1是翻转\n",
    "        self.lazy = 0\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.val = 0\n",
    "\n",
    "\n",
    "def push_up(node):\n",
    "    node.val = node.left.val + node.right.val\n",
    "\n",
    "\n",
    "def push_down(node):\n",
    "    if node.left is None:\n",
    "        node.left = Node(node.l, node.mid)\n",
    "    if node.right is None:\n",
    "        node.right = Node(node.mid + 1, node.r)\n",
    "    if node.lazy:\n",
    "        node.lazy = 0\n",
    "        node.left.lazy ^= 1\n",
    "        node.right.lazy ^= 1\n",
    "        node.left.val = node.left.leng - node.left.val\n",
    "        node.right.val = node.right.leng - node.right.val\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        root = Node(0, n - 1)\n",
    "\n",
    "        def build(node):\n",
    "            if node.l == node.r:\n",
    "                node.val = nums1[node.l]\n",
    "                return\n",
    "            push_down(node)\n",
    "            build(node.left)\n",
    "            build(node.right)\n",
    "            push_up(node)\n",
    "\n",
    "        build(root)\n",
    "        ans = []\n",
    "        s = sum(nums2)\n",
    "        self.root = root\n",
    "        for u, l, r in queries:\n",
    "            if u == 1:\n",
    "                self.update(l, r)\n",
    "            elif u == 2:\n",
    "                s += self.root.val * l\n",
    "            else:\n",
    "                ans.append(s)\n",
    "        return ans\n",
    "\n",
    "    def update(self, l: int, r: int, node: 'Node' = None):\n",
    "        if node is None:\n",
    "            node = self.root\n",
    "        if l <= node.l and node.r <= r:\n",
    "            node.val = node.leng - node.val\n",
    "            node.lazy ^= 1\n",
    "            return\n",
    "        # 本处是为了推送lazy,而不再是为了开点了(build时候满二叉树),其实此处已经蕴含了查询功能了,push_down到更改的最小区间,push_up到上方影响区间\n",
    "        push_down(node)\n",
    "        if l <= node.mid:\n",
    "            self.update(l, r, node.left)\n",
    "        if r > node.mid:\n",
    "            self.update(l, r, node.right)\n",
    "        push_up(node)\n",
    "\n",
    "# 作者：Athanasy\n",
    "# 链接：https://leetcode.cn/circle/discuss/zBFNp0/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class STNode():\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.sum = 0\n",
    "        self.lazy = False\n",
    "    \n",
    "    def update(self, l, r, i, j):\n",
    "        # base case\n",
    "        if i <= l and r <= j:\n",
    "            self.lazy = not self.lazy\n",
    "            self.sum = (r - l + 1) - self.sum\n",
    "            return\n",
    "        mid = (l + r) // 2\n",
    "        self.push_down(l, r, mid)\n",
    "        if i <= mid:\n",
    "            self.left.update(l, mid, i, j)\n",
    "        if j > mid:\n",
    "            self.right.update(mid + 1, r, i, j)\n",
    "        self.pop_up()\n",
    "    \n",
    "    def query(self, l, r, i, j):\n",
    "        # base case\n",
    "        if i <= l and r <= j:\n",
    "            return self.sum\n",
    "        mid = (l + r) // 2\n",
    "        self.push_down(l, r, mid)\n",
    "        res = 0\n",
    "        if i <= mid:\n",
    "            res += self.query(l, mid, i, j)\n",
    "        if j > mid:\n",
    "            res += self.query(mid + 1, r, i, j)\n",
    "        return res\n",
    "\n",
    "    def push_down(self, l, r, mid):\n",
    "        if self.left is None:\n",
    "            self.left = STNode()\n",
    "        if self.right is None:\n",
    "            self.right = STNode()\n",
    "        if self.lazy:\n",
    "            self.left.lazy = not self.left.lazy\n",
    "            self.left.sum = (mid - l + 1) - self.left.sum\n",
    "            self.right.lazy = not self.right.lazy\n",
    "            self.right.sum = (r - mid) - self.right.sum\n",
    "            self.lazy = False\n",
    "\n",
    "    def pop_up(self):\n",
    "        self.sum = self.left.sum + self.right.sum\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        tree = STNode()\n",
    "        n = len(nums1)\n",
    "        for i, num in enumerate(nums1):\n",
    "            if num == 1:\n",
    "                tree.update(0, n + 1, i, i)\n",
    "        \n",
    "        sum2 = 0\n",
    "        for i, num in enumerate(nums2):\n",
    "            sum2 += num\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(len(queries)):\n",
    "            if queries[i][0] == 1:\n",
    "                l = queries[i][1]\n",
    "                r = queries[i][2]\n",
    "                tree.update(0, n + 1, l, r)\n",
    "            elif queries[i][0] == 2:\n",
    "                sum2 += (tree.sum * queries[i][1])\n",
    "            else:\n",
    "                ans.append(sum2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        tree = [0]*(4*n)\n",
    "        def build(t,l,r):\n",
    "            if(l == r):\n",
    "                tree[t] = [nums1[l], l, r, 0]\n",
    "                return\n",
    "            m = (l+r)>>1\n",
    "            build(2*t,l,m)\n",
    "            build(2*t+1,m+1,r)\n",
    "            tree[t] = [tree[2*t][0]+tree[2*t+1][0],l,r,0]\n",
    "            return\n",
    "        \n",
    "        def pushdown(t):\n",
    "            lazy = tree[t][3]\n",
    "            tree[2*t][3] ^= lazy\n",
    "            tree[2*t][0] = tree[2*t][2] - tree[2*t][1] + 1 - tree[2*t][0]\n",
    "            tree[2*t+1][3] ^= lazy\n",
    "            tree[2*t+1][0] = tree[2*t+1][2] - tree[2*t+1][1] + 1 - tree[2*t+1][0]\n",
    "            tree[t][3] = 0\n",
    "            return\n",
    "\n",
    "        def update(t,ul,ur):\n",
    "            v, l, r, lazy = tree[t]\n",
    "            if(ul <= l and r <= ur):\n",
    "                tree[t][0] = r - l + 1 - tree[t][0]\n",
    "                tree[t][3] ^= 1\n",
    "                return\n",
    "            if(lazy != 0):\n",
    "                pushdown(t)\n",
    "            m = (l+r)>>1\n",
    "            if(ul <= m):\n",
    "                update(2*t,ul,ur)\n",
    "            if(ur > m):\n",
    "                update(2*t+1,ul,ur)\n",
    "            tree[t][0] = tree[2*t][0]+tree[2*t+1][0]\n",
    "            return \n",
    "        def query(t,ql,qr):\n",
    "            v, l, r, lazy = tree[t]\n",
    "            if(ql <= l and r <= qr):\n",
    "                return v \n",
    "            if(lazy != 0):\n",
    "                pushdown(t)\n",
    "            m = (l+r)>>1\n",
    "            rsum = 0\n",
    "            if(ql <= m):\n",
    "                rsum += query(2*t,ql,qr)\n",
    "            if(qr > m):\n",
    "                rsum += query(2*t+1,ql,qr)\n",
    "            return rsum\n",
    "        build(1,0,n-1)\n",
    "        row_sum = sum(nums2)\n",
    "        result = []\n",
    "        for tp,l,r in queries:\n",
    "            if(tp == 1):\n",
    "                update(1,l,r)\n",
    "            elif(tp == 2):\n",
    "                row_sum += l * query(1,0,n-1)\n",
    "            else:\n",
    "                result.append(row_sum)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        tree = [0]*(4*n)\n",
    "        def build(t,l,r):\n",
    "            if(l == r):\n",
    "                tree[t] = [nums1[l], l, r, 0]\n",
    "                return\n",
    "            m = (l+r)>>1\n",
    "            build(2*t,l,m)\n",
    "            build(2*t+1,m+1,r)\n",
    "            tree[t] = [tree[2*t][0]+tree[2*t+1][0],l,r,0]\n",
    "            return\n",
    "        \n",
    "        def pushdown(t):\n",
    "            lazy = tree[t][3]\n",
    "            tree[2*t][3] ^= lazy\n",
    "            tree[2*t][0] = tree[2*t][2] - tree[2*t][1] + 1 - tree[2*t][0]\n",
    "            tree[2*t+1][3] ^= lazy\n",
    "            tree[2*t+1][0] = tree[2*t+1][2] - tree[2*t+1][1] + 1 - tree[2*t+1][0]\n",
    "            tree[t][3] = 0\n",
    "            return\n",
    "\n",
    "        def update(t,ul,ur):\n",
    "            v, l, r, lazy = tree[t]\n",
    "            if(ul <= l and r <= ur):\n",
    "                tree[t][0] = r - l + 1 - tree[t][0]\n",
    "                tree[t][3] ^= 1\n",
    "                return\n",
    "            if(lazy != 0):\n",
    "                pushdown(t)\n",
    "            m = (l+r)>>1\n",
    "            if(ul <= m):\n",
    "                update(2*t,ul,ur)\n",
    "            if(ur > m):\n",
    "                update(2*t+1,ul,ur)\n",
    "            tree[t][0] = tree[2*t][0]+tree[2*t+1][0]\n",
    "            return \n",
    "        def query(t,ql,qr):\n",
    "            v, l, r, lazy = tree[t]\n",
    "            if(ql <= l and r <= qr):\n",
    "                return v \n",
    "            if(lazy != 0):\n",
    "                pushdown(t)\n",
    "            m = (l+r)>>1\n",
    "            rsum = 0\n",
    "            if(ql <= m):\n",
    "                rsum += query(2*t,ql,qr)\n",
    "            if(qr > m):\n",
    "                rsum += query(2*t+1,ql,qr)\n",
    "            return rsum\n",
    "        build(1,0,n-1)\n",
    "        row_sum = sum(nums2)\n",
    "        result = []\n",
    "        for tp,l,r in queries:\n",
    "            if(tp == 1):\n",
    "                update(1,l,r)\n",
    "            elif(tp == 2):\n",
    "                row_sum += l * query(1,0,n-1)\n",
    "            else:\n",
    "                result.append(row_sum)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        tree = [0]*(4*n)\n",
    "        def build(t,l,r):\n",
    "            if(l == r):\n",
    "                tree[t] = [nums1[l], l, r, 0]\n",
    "                return\n",
    "            m = (l+r)>>1\n",
    "            build(2*t,l,m)\n",
    "            build(2*t+1,m+1,r)\n",
    "            tree[t] = [tree[2*t][0]+tree[2*t+1][0],l,r,0]\n",
    "            return\n",
    "        \n",
    "        def pushdown(t):\n",
    "            lazy = tree[t][3]\n",
    "            tree[2*t][3] ^= lazy\n",
    "            tree[2*t][0] = tree[2*t][2] - tree[2*t][1] + 1 - tree[2*t][0]\n",
    "            tree[2*t+1][3] ^= lazy\n",
    "            tree[2*t+1][0] = tree[2*t+1][2] - tree[2*t+1][1] + 1 - tree[2*t+1][0]\n",
    "            tree[t][3] = 0\n",
    "            return\n",
    "\n",
    "        def update(t,ul,ur):\n",
    "            v, l, r, lazy = tree[t]\n",
    "            if(ul <= l and r <= ur):\n",
    "                tree[t][0] = r - l + 1 - tree[t][0]\n",
    "                tree[t][3] ^= 1\n",
    "                return\n",
    "            if(lazy != 0):\n",
    "                pushdown(t)\n",
    "            m = (l+r)>>1\n",
    "            if(ul <= m):\n",
    "                update(2*t,ul,ur)\n",
    "            if(ur > m):\n",
    "                update(2*t+1,ul,ur)\n",
    "            tree[t][0] = tree[2*t][0]+tree[2*t+1][0]\n",
    "            return \n",
    "        def query(t,ql,qr):\n",
    "            v, l, r, lazy = tree[t]\n",
    "            if(ql <= l and r <= qr):\n",
    "                return v \n",
    "            if(lazy != 0):\n",
    "                pushdown(t)\n",
    "            m = (l+r)>>1\n",
    "            rsum = 0\n",
    "            if(ql <= m):\n",
    "                rsum += query(2*t,ql,qr)\n",
    "            if(qr > m):\n",
    "                rsum += query(2*t+1,ql,qr)\n",
    "            return rsum\n",
    "        build(1,0,n-1)\n",
    "        row_sum = sum(nums2)\n",
    "        result = []\n",
    "        for tp,l,r in queries:\n",
    "            if(tp == 1):\n",
    "                update(1,l,r)\n",
    "            elif(tp == 2):\n",
    "                row_sum += l * query(1,0,n-1)\n",
    "            else:\n",
    "                result.append(row_sum)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class LazySegmentTree:\n",
    "    def __init__(self, l, r):\n",
    "        self.l = l\n",
    "        self.r = r\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.sum = 0\n",
    "        self.delay = False\n",
    "        \n",
    "    def _update_lazy(self):\n",
    "        self.delay = 0\n",
    "        self.left.delay = not self.left.delay\n",
    "        self.left.sum = self.left.r - self.left.l + 1 - self.left.sum\n",
    "        self.right.delay = not self.right.delay\n",
    "        self.right.sum = self.right.r - self.right.l + 1 - self.right.sum\n",
    "\n",
    "    def update(self, L, R):\n",
    "        if L <= self.l and self.r <= R:\n",
    "            self.sum = self.r - self.l + 1 - self.sum\n",
    "            self.delay = not self.delay\n",
    "            return\n",
    "        \n",
    "        mid = self.l + ((self.r - self.l)>>1)\n",
    "        if self.left is None:\n",
    "            self.left = LazySegmentTree(self.l, mid)\n",
    "            self.right = LazySegmentTree(mid+1, self.r)\n",
    "        \n",
    "        if self.delay:\n",
    "           self._update_lazy()\n",
    "            \n",
    "        if mid >= L:\n",
    "            self.left.update(L, R)\n",
    "        \n",
    "        if mid + 1 <= R:\n",
    "            self.right.update(L, R)\n",
    "        \n",
    "        self.sum = self.left.sum + self.right.sum\n",
    "        \n",
    "    def query(self, L, R):\n",
    "        if L <= self.l and self.r <= R:\n",
    "            return self.sum\n",
    "        \n",
    "        mid = self.l + ((self.r - self.l)>>1)\n",
    "        if self.left is None:\n",
    "            self.left = LazySegmentTree(self.l, mid)\n",
    "            self.right = LazySegmentTree(mid+1, self.r)\n",
    "\n",
    "        if self.delay:\n",
    "            self._update_lazy()\n",
    "\n",
    "        ans = 0\n",
    "        if mid >= L:\n",
    "            ans += self.left.query(L, R)\n",
    "            \n",
    "        if mid + 1 <= R:\n",
    "            ans += self.right.query(L, R)\n",
    "        \n",
    "        return ans\n",
    "    \n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        st = LazySegmentTree(0, n)\n",
    "        for i, v in enumerate(nums1):\n",
    "            if v:\n",
    "                st.update(i, i)\n",
    "        s = st.query(0, n)\n",
    "        s2 = sum(nums2)\n",
    "        ans = []\n",
    "        for q, l, r in queries:\n",
    "            if q == 1:\n",
    "                st.update(l, r)\n",
    "            elif q == 2:\n",
    "                if l == 0:\n",
    "                    continue\n",
    "                s = st.query(0, n)\n",
    "                s2 += l * s\n",
    "            else:\n",
    "                ans.append(s2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegTreeNode:\n",
    "    def __init__(self, a, b, val):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.start = a\n",
    "        self.end = b\n",
    "        self.info = 0  # the sum value over the range\n",
    "        self.lazy_tag = False  # if the child ranges are pending propagation\n",
    "        self.lazy_val = 0  # how many flips needed to be propagated to child ranges.\n",
    "\n",
    "        if a == b:\n",
    "            self.info = val[a]\n",
    "            return\n",
    "\n",
    "        mid = (a + b) // 2\n",
    "        if self.left is None:\n",
    "            self.left = SegTreeNode(a, mid, val)\n",
    "            self.right = SegTreeNode(mid + 1, b, val)\n",
    "            self.info = self.left.info + self.right.info\n",
    "\n",
    "    def push_down(self):\n",
    "        if self.lazy_tag and self.left:\n",
    "            if self.lazy_val % 2 == 1:\n",
    "                self.left.info = (self.left.end - self.left.start + 1) - self.left.info\n",
    "                self.right.info = (self.right.end - self.right.start + 1) - self.right.info\n",
    "                self.left.lazy_tag = True\n",
    "                self.left.lazy_val += self.lazy_val\n",
    "                self.right.lazy_tag = True\n",
    "                self.right.lazy_val += self.lazy_val\n",
    "\n",
    "            self.lazy_tag = False\n",
    "            self.lazy_val = 0\n",
    "\n",
    "    def update_range(self, a, b):\n",
    "        if b < self.start or a > self.end:\n",
    "            return\n",
    "\n",
    "        if a <= self.start and self.end <= b:\n",
    "            self.info = (self.end - self.start + 1) - self.info\n",
    "            self.lazy_tag = True\n",
    "            self.lazy_val += 1\n",
    "            return\n",
    "\n",
    "        if self.left:\n",
    "            self.push_down()\n",
    "            self.left.update_range(a, b)\n",
    "            self.right.update_range(a, b)\n",
    "            self.info = self.left.info + self.right.info\n",
    "\n",
    "    def query_range(self, a, b):\n",
    "        if b < self.start or a > self.end:\n",
    "            return 0\n",
    "\n",
    "        if a <= self.start and self.end <= b:\n",
    "            return self.info\n",
    "\n",
    "        if self.left:\n",
    "            self.push_down()\n",
    "            ret = self.left.query_range(a, b) + self.right.query_range(a, b)\n",
    "            self.info = self.left.info + self.right.info\n",
    "            return ret\n",
    "\n",
    "        return self.info\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        root = SegTreeNode(0, n - 1, nums1)\n",
    "        total_sum = sum(nums2)\n",
    "        rets = []\n",
    "\n",
    "        for query in queries:\n",
    "            if query[0] == 1:\n",
    "                root.update_range(query[1], query[2])\n",
    "            elif query[0] == 2:\n",
    "                total_sum += root.query_range(0, n - 1) * query[1]\n",
    "            else:\n",
    "                rets.append(total_sum)\n",
    "\n",
    "        return rets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        seg_tree = [[-1] * 4 for _ in range(n * 4)]\n",
    "        self.create_tree(nums1, seg_tree, 1, 0, n - 1)\n",
    "        answer = []\n",
    "        sum2 = sum(nums2)\n",
    "        for q in queries:\n",
    "            if q[0] == 1:\n",
    "                self.update_tree(seg_tree, 1, q[1], q[2])\n",
    "            elif q[0] == 2:\n",
    "                sum2 += q[1] * seg_tree[1][2]\n",
    "            else:\n",
    "                answer.append(sum2)\n",
    "        return answer\n",
    "\n",
    "    def create_tree(\n",
    "        self,\n",
    "        nums: List[int],\n",
    "        seg_tree: List[List[int]],\n",
    "        pos: int,\n",
    "        left: int,\n",
    "        right: int,\n",
    "    ) -> None:\n",
    "        seg_tree[pos][0] = left\n",
    "        seg_tree[pos][1] = right\n",
    "        seg_tree[pos][3] = 0\n",
    "        if left == right:\n",
    "            seg_tree[pos][2] = nums[left]\n",
    "        else:\n",
    "            mid = (left + right) // 2\n",
    "            self.create_tree(nums, seg_tree, pos * 2, left, mid)\n",
    "            self.create_tree(nums, seg_tree, pos * 2 + 1, mid + 1, right)\n",
    "            seg_tree[pos][2] = seg_tree[pos * 2][2] + seg_tree[pos * 2 + 1][2]\n",
    "\n",
    "    def update_tree(\n",
    "        self,\n",
    "        seg_tree: List[List[int]],\n",
    "        pos: int,\n",
    "        q_left: int,\n",
    "        q_right: int,\n",
    "    ) -> int:\n",
    "        left, right = seg_tree[pos][0], seg_tree[pos][1]\n",
    "        if q_left <= left and q_right >= right:\n",
    "            return self.flip(seg_tree, pos)\n",
    "        mid = (left + right) // 2\n",
    "        delta = 0\n",
    "        if seg_tree[pos][3] == 1:\n",
    "            self.flip(seg_tree, pos * 2)\n",
    "            self.flip(seg_tree, pos * 2 + 1)\n",
    "            seg_tree[pos][3] = 0\n",
    "        if q_left <= mid:\n",
    "            delta += self.update_tree(seg_tree, pos * 2, q_left, min(q_right, mid))\n",
    "        if q_right >= mid + 1:\n",
    "            delta += self.update_tree(\n",
    "                seg_tree, pos * 2 + 1, max(mid + 1, q_left), q_right\n",
    "            )\n",
    "        seg_tree[pos][2] += delta\n",
    "        return delta\n",
    "\n",
    "    def flip(self, seg_tree: List[List[int]], pos: int) -> int:\n",
    "        left, right, val, kid_lazy_flip = seg_tree[pos]\n",
    "        new_val = right - left + 1 - val\n",
    "        delta = new_val - val\n",
    "        seg_tree[pos][2] = new_val\n",
    "        seg_tree[pos][3] = 1 - kid_lazy_flip\n",
    "        return delta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "    函数         递归前             回溯时\n",
    "    build()                       push_up()\n",
    "    query()     push_down()\n",
    "   modify()     push_down()       push_up()\n",
    "'''\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, l: int, r: int, v: int = 0, lazy: bool = False):\n",
    "        self.l = l\n",
    "        self.r = r\n",
    "        self.v = v\n",
    "        self.lazy = lazy\n",
    "\n",
    "\n",
    "def push_up(u: int):\n",
    "    tree[u].v = tree[u << 1].v + tree[u << 1 | 1].v        #求区间和\n",
    "    #tree[u].v = max(tree[u << 1].v, tree[u << 1 | 1].v)     #求区间max\n",
    "    #tree[u].v = min(tree[u << 1].v, tree[u << 1 | 1].v)     #求区间min\n",
    "\n",
    "#lazy 标记表示 对以u为根(不包括根)的所有子树生效\n",
    "def do(u):\n",
    "    cur = tree[u]\n",
    "    cur.v = cur.r - cur.l + 1 - cur.v\n",
    "    cur.lazy = not cur.lazy\n",
    "\n",
    "\n",
    "\n",
    "#以数组data为值时,建立与之对应值为v的树\n",
    "def build(u: int, l: int, r: int, data: []) -> None:\n",
    "    if l == r:\n",
    "        tree[u] = Node(l, r, data[l - 1])\n",
    "        return\n",
    "    tree[u] = Node(l, r)\n",
    "    mid = l + r >> 1\n",
    "    build(u << 1, l, mid, data)\n",
    "    build(u << 1 | 1, mid + 1, r, data)\n",
    "    push_up(u)\n",
    "\n",
    "def modify(u: int, l: int, r: int, val: bool):\n",
    "    cur = tree[u]\n",
    "    if l <= cur.l and cur.r <= r:\n",
    "        do(u)\n",
    "        return \n",
    "    mid = cur.l + cur.r >> 1\n",
    "    if cur.lazy:\n",
    "        do(u << 1)\n",
    "        do(u << 1 | 1)\n",
    "        cur.lazy = False\n",
    "    \n",
    "    if l <= mid: modify(u << 1, l, r, val)\n",
    "    if r > mid: modify(u << 1 | 1, l, r, val)\n",
    "    push_up(u)\n",
    "\n",
    "tree = [0] * (4 * 10 ** 5 + 10)\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        \n",
    "        build(1, 1, n, nums1)\n",
    "        cur = sum(nums2)\n",
    "        res = []\n",
    "        for op, l, r in queries:\n",
    "            if op == 1: modify(1, l + 1, r + 1, True)\n",
    "            elif op == 2: cur += tree[1].v * l\n",
    "            else: res.append(cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "    函数         递归前             回溯时\n",
    "    build()                       push_up()\n",
    "    query()     push_down()\n",
    "   modify()     push_down()       push_up()\n",
    "'''\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, l: int, r: int, v: int = 0, lazy: int = 0):\n",
    "        self.l = l\n",
    "        self.r = r\n",
    "        self.v = v\n",
    "        self.lazy = lazy\n",
    "\n",
    "\n",
    "N = 100\n",
    "tree = [None for _ in range(4 * N)]\n",
    "\n",
    "def push_up(u: int):\n",
    "    tree[u].v = tree[u << 1].v + tree[u << 1 | 1].v          #求区间和\n",
    "    #tree[u].v = max(tree[u << 1].v, tree[u << 1 | 1].v)     #求区间max\n",
    "    #tree[u].v = min(tree[u << 1].v, tree[u << 1 | 1].v)     #求区间min\n",
    "\n",
    "#lazy 标记表示 对以u为根(不包括根)的所有子树生效\n",
    "def push_down(u: int):\n",
    "    cur, left, right = tree[u], tree[u << 1], tree[u << 1 | 1]\n",
    "    if cur.lazy == 0: return\n",
    "    mid = cur.l + cur.r >> 1\n",
    "\n",
    "    left.v = (mid - cur.l + 1) - left.v\n",
    "    right.v = (cur.r - mid) - right.v\n",
    "\n",
    "    left.lazy ^= cur.lazy\n",
    "    right.lazy ^= cur.lazy\n",
    "    cur.lazy = 0\n",
    "\n",
    "\n",
    "#data下标从1开始\n",
    "#以数组data为值时,建立与之对应值为v的树\n",
    "def build(u: int, l: int, r: int, data: []) -> None:\n",
    "    if l == r:\n",
    "        tree[u] = Node(l, r, data[l - 1])\n",
    "        return\n",
    "    tree[u] = Node(l, r)\n",
    "    mid = l + r >> 1\n",
    "    build(u << 1, l, mid, data)\n",
    "    build(u << 1 | 1, mid + 1, r, data)\n",
    "    push_up(u)\n",
    "\n",
    "def modify(u: int, l: int, r: int, val: int):\n",
    "    cur = tree[u]\n",
    "    if l <= cur.l and cur.r <= r:\n",
    "        cur.v = (cur.r - cur.l + 1) - cur.v\n",
    "        cur.lazy ^= val\n",
    "        return\n",
    "\n",
    "    push_down(u)\n",
    "    mid = cur.l + cur.r >> 1\n",
    "    if l <= mid: modify(u << 1, l, r, val)\n",
    "    if r > mid: modify(u << 1 | 1, l, r, val)\n",
    "    push_up(u)\n",
    "\n",
    "tree = [0] * (4 * 10 ** 5 + 10)\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        \n",
    "        build(1, 1, n, nums1)\n",
    "        cur = sum(nums2)\n",
    "        res = []\n",
    "        for op, l, r in queries:\n",
    "            if op == 1: modify(1, l + 1, r + 1, 1)\n",
    "            elif op == 2: cur += tree[1].v * l\n",
    "            else: res.append(cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, start, end):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "        self.total = 0\n",
    "        self.left = self.right = None\n",
    "        self.to_flip = False\n",
    "\n",
    "class NumArray:\n",
    "    def __init__(self, nums):\n",
    "        def createTree(nums, l, r):\n",
    "            if l > r: return None\n",
    "            if l == r:\n",
    "                n = Node(l, r)\n",
    "                n.total = nums[l]\n",
    "                return n\n",
    "            mid = (l + r) // 2\n",
    "            root = Node(l, r)\n",
    "            root.left = createTree(nums, l, mid)\n",
    "            root.right = createTree(nums, mid + 1, r)\n",
    "            root.total = root.left.total + root.right.total\n",
    "            return root\n",
    "\n",
    "        self.root = createTree(nums, 0, len(nums) - 1)\n",
    "\n",
    "    def flip(self, root):\n",
    "        root.total = (root.end - root.start + 1) - root.total\n",
    "        root.to_flip = not root.to_flip\n",
    "\n",
    "    def push(self, root):\n",
    "        if root.to_flip:\n",
    "            if root.left:\n",
    "                self.flip(root.left)\n",
    "            if root.right:\n",
    "                self.flip(root.right)\n",
    "            root.to_flip = False\n",
    "\n",
    "    def updateRange(self, i, j):\n",
    "        def updater(root, i, j):\n",
    "            if root.start > j or root.end < i: return\n",
    "            if i <= root.start and j >= root.end:\n",
    "                self.flip(root)\n",
    "                return\n",
    "            self.push(root)\n",
    "            updater(root.left, i, j)\n",
    "            updater(root.right, i, j)\n",
    "            root.total = root.left.total + root.right.total\n",
    "\n",
    "        updater(self.root, i, j)\n",
    "\n",
    "    def sumRange(self, i, j):\n",
    "        def rangeSum(root, i, j):\n",
    "            if root.start > j or root.end < i: return 0\n",
    "            if i <= root.start and j >= root.end: return root.total\n",
    "            self.push(root)\n",
    "            return rangeSum(root.left, i, j) + rangeSum(root.right, i, j)\n",
    "\n",
    "        return rangeSum(self.root, i, j)\n",
    "\n",
    "# Test\n",
    "# nums = [1,0,0,1,0]\n",
    "# numArray = NumArray(nums)\n",
    "# print(numArray.sumRange(0, 4))  # Output: 2\n",
    "# numArray.updateRange(0, 4)\n",
    "# print(numArray.sumRange(0, 4))  # Output: 3\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n1 = len(nums1)\n",
    "        numArray = NumArray(nums1)\n",
    "        s2 = sum(nums2)\n",
    "        res = list()\n",
    "        for t, l, r in queries:\n",
    "            if t == 1:\n",
    "                numArray.updateRange(l, r)\n",
    "            elif t == 2:\n",
    "                s2 += l * numArray.sumRange(0, n1 - 1)\n",
    "            else:\n",
    "                res.append(s2)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(\n",
    "        self, nums1: list[int], nums2: list[int], queries: list[list[int]]\n",
    "    ) -> list[int]:\n",
    "        output: list[int] = []\n",
    "        nums1_tree = SegmentTree(nums1)\n",
    "        nums2_sum = sum(nums2)\n",
    "        for op in queries:\n",
    "            match op[0]:\n",
    "                case 1:\n",
    "                    nums1_tree.update(op[1], op[2])\n",
    "                case 2:\n",
    "                    nums2_sum += nums1_tree.query(0, len(nums1) - 1) * op[1]\n",
    "                case 3:\n",
    "                    output.append(nums2_sum)\n",
    "        return output\n",
    "\n",
    "\n",
    "class SegmentTree:\n",
    "    \"\"\"线段树\"\"\"\n",
    "\n",
    "    def __init__(self, arr: list) -> None:\n",
    "        self.arr = arr\n",
    "        self.len = len(arr)\n",
    "        self.tree = [SegNode() for _ in range(self.len * 4)]\n",
    "        self._build(0, 0, self.len - 1)\n",
    "\n",
    "    def _build(self, node_id: int, left_b: int, right_b: int):\n",
    "        \"\"\"构造线段树\"\"\"\n",
    "        node = self.tree[node_id]\n",
    "        if left_b == right_b:\n",
    "            node.val = self.arr[left_b]\n",
    "        else:\n",
    "            mid = (left_b + right_b) // 2\n",
    "            self._build(node_id * 2 + 1, left_b, mid)\n",
    "            self._build(node_id * 2 + 2, mid + 1, right_b)\n",
    "            node.val = self.tree[node_id * 2 + 1].val + self.tree[node_id * 2 + 2].val\n",
    "            node.length = right_b - left_b + 1\n",
    "\n",
    "    def query(self, start: int, end: int):\n",
    "        \"\"\"查询结点\"\"\"\n",
    "        return self._query(0, 0, self.len - 1, start, end)\n",
    "\n",
    "    def _query(self, node_id: int, left_b: int, right_b: int, start: int, end: int):\n",
    "        # 没有交集\n",
    "        if left_b > end or right_b < start:\n",
    "            return 0\n",
    "\n",
    "        if self.tree[node_id].lazy_op:\n",
    "            self.pushdown(node_id)\n",
    "        # 完全覆盖\n",
    "        if left_b >= start and right_b <= end:\n",
    "            return self.tree[node_id].val\n",
    "        # 存在交集，但没有完全覆盖\n",
    "        mid = (left_b + right_b) // 2\n",
    "        leftval, rightval = 0, 0\n",
    "        if mid >= start:\n",
    "            leftval = self._query(node_id * 2 + 1, left_b, mid, start, end)\n",
    "        if mid + 1 <= end:\n",
    "            rightval = self._query(node_id * 2 + 2, mid + 1, right_b, start, end)\n",
    "        return leftval + rightval\n",
    "\n",
    "    def update(self, start: int, end: int):\n",
    "        \"\"\"更新结点\"\"\"\n",
    "        self._update(0, 0, self.len - 1, start, end)\n",
    "\n",
    "    def _update(\n",
    "        self,\n",
    "        node_id: int,\n",
    "        left_b: int,\n",
    "        right_b: int,\n",
    "        start: int,\n",
    "        end: int,\n",
    "    ):\n",
    "        \"\"\"\"\"\"\n",
    "        # 没有交集\n",
    "        if left_b > end or right_b < start:\n",
    "            return\n",
    "\n",
    "        node = self.tree[node_id]\n",
    "        if node.lazy_op:\n",
    "            self.pushdown(node_id)\n",
    "        # 完全覆盖\n",
    "        if left_b >= start and right_b <= end:\n",
    "            node.val = node.length - node.val\n",
    "            node.lazy_op = True\n",
    "            return\n",
    "        # 存在交集，但没有完全覆盖\n",
    "\n",
    "        mid = (left_b + right_b) // 2\n",
    "        if mid >= start:\n",
    "            self._update(node_id * 2 + 1, left_b, mid, start, end)\n",
    "        if mid + 1 <= end:\n",
    "            self._update(node_id * 2 + 2, mid + 1, right_b, start, end)\n",
    "        node.val = self.tree[node_id * 2 + 1].val + self.tree[node_id * 2 + 2].val\n",
    "\n",
    "    def pushdown(self, node_id: int):\n",
    "        \"\"\"修改并下传标记\"\"\"\n",
    "        parent = self.tree[node_id]\n",
    "        if node_id * 2 + 2 < self.len * 4:\n",
    "            left = self.tree[node_id * 2 + 1]\n",
    "            right = self.tree[node_id * 2 + 2]\n",
    "            # if left.lazy_op:\n",
    "            #     self.pushdown(node_id * 2 + 1)\n",
    "            left.val = left.length - left.val\n",
    "            # if right.lazy_op:\n",
    "            #     self.pushdown(node_id * 2 + 2)\n",
    "            right.val = right.length - right.val\n",
    "            left.lazy_op, right.lazy_op = not left.lazy_op, not right.lazy_op\n",
    "        parent.lazy_op = False\n",
    "\n",
    "class SegNode:\n",
    "    \"\"\"结点\"\"\"\n",
    "\n",
    "    def __init__(self, val=0, length=1):\n",
    "        self.val = val\n",
    "        self.length = length\n",
    "        self.lazy_op: bool = False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ret = []\n",
    "        sum2 = sum(nums2)\n",
    "        tree = SegTree(nums1)\n",
    "        for x0, x1, x2 in queries:\n",
    "            if x0==1:\n",
    "                tree.modify(0, x1, x2)\n",
    "            elif x0==2:\n",
    "                sum2 += tree.arr[0].sum*x1\n",
    "                # sum2 += tree.query(0, 0, len(nums1)-1)*x1\n",
    "            else:\n",
    "                ret.append(sum2)\n",
    "\n",
    "        return ret\n",
    "\n",
    "class SegNode:\n",
    "    def __init__(self):\n",
    "        self.l = 0\n",
    "        self.r = 0\n",
    "        self.sum = 0\n",
    "        self.lazy = False\n",
    "\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self, nums1):\n",
    "        # 初始化数组\n",
    "        self.arr = [SegNode() for _ in range(4*len(nums1))]\n",
    "        # 开始id，左边界，右边界\n",
    "        self.build(0, 0, len(nums1)-1, nums1)\n",
    "\n",
    "    def build(self, i, l, r, nums1):\n",
    "\n",
    "        # NOTE1 这个很重要，非常非常重要\n",
    "        self.arr[i].l = l\n",
    "        self.arr[i].r = r\n",
    "\n",
    "        if l==r:\n",
    "            self.arr[i].sum = nums1[l]\n",
    "            return\n",
    "\n",
    "        mid = l + ((r-l)>>1)\n",
    "\n",
    "        self.build(2*i+1, l, mid, nums1)\n",
    "        self.build(2*i+2, mid+1, r, nums1)\n",
    "\n",
    "        self.arr[i].sum = self.arr[2*i+1].sum + self.arr[2*i+2].sum\n",
    "\n",
    "    def push_down(self, i):\n",
    "        if self.arr[i].lazy:\n",
    "            \n",
    "            self.arr[2*i+1].lazy = not self.arr[2*i+1].lazy\n",
    "            self.arr[2*i+1].sum = self.arr[2*i+1].r-self.arr[2*i+1].l+1-self.arr[2*i+1].sum\n",
    "\n",
    "            self.arr[2*i+2].lazy = not self.arr[2*i+2].lazy\n",
    "            self.arr[2*i+2].sum = self.arr[2*i+2].r-self.arr[2*i+2].l+1-self.arr[2*i+2].sum  # NOTE2 这里下标写错了，写成2*i+1\n",
    "\n",
    "            self.arr[i].lazy = False\n",
    "\n",
    "    def modify(self, i, l, r):\n",
    "        if self.arr[i].l >= l and self.arr[i].r <= r:\n",
    "            # 当前区间完全被待修改区间包含\n",
    "            self.arr[i].sum = self.arr[i].r-self.arr[i].l+1-self.arr[i].sum\n",
    "            self.arr[i].lazy = not self.arr[i].lazy\n",
    "            return\n",
    "        \n",
    "        self.push_down(i)\n",
    "        \n",
    "        # 最开始是这样写的self.arr[i].l>=l\n",
    "        # print(i, 2*i+1,self.arr[2*i+1].r,l, self.arr[2*i+2].l,r)\n",
    "        if self.arr[2*i+1].r>=l:\n",
    "            self.modify(2*i+1, l, r)\n",
    "        if self.arr[2*i+2].l<=r:\n",
    "            self.modify(2*i+2, l, r)\n",
    "    \n",
    "        self.arr[i].sum = self.arr[2*i+1].sum+self.arr[2*i+2].sum\n",
    "\n",
    "    # def query(self, i, l, r):\n",
    "    #     if self.arr[i].l >= l and self.arr[i].r <= r:\n",
    "    #         return self.arr[i].sum\n",
    "    #     if self.arr[i].r<l or self.arr[i].l>r:\n",
    "    #         return 0\n",
    "\n",
    "    #     self.push_down(i)        \n",
    "    #     ret = 0\n",
    "    #     if self.arr[2*i+1].r>=l:\n",
    "    #         res+= self.query(2*i+1, l, r)\n",
    "    #     if self.arr[2*i+2].l<=r:\n",
    "    #         res+= self.query(2*i+2, l, r)\n",
    "    \n",
    "    #     return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        ans = []\n",
    "        segtree = SegTree(nums1)\n",
    "        cur_sum = sum(nums2)\n",
    "\n",
    "        for q in queries:\n",
    "            if q[0] == 1:\n",
    "                segtree.modify(q[1], q[2], 1)\n",
    "            elif q[0] == 2:\n",
    "                cur_sum += segtree.total()*q[1]\n",
    "            elif q[0] == 3:\n",
    "                ans.append(cur_sum)\n",
    "\n",
    "        return ans\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self, nums):\n",
    "        self.n = len(nums)\n",
    "        self.arr = [SegNode() for _ in range(self.n*4+1)]\n",
    "        self.build(0, self.n-1, 1, nums)\n",
    "    \n",
    "    def build(self, l, r, p, nums):\n",
    "\n",
    "        self.arr[p].l = l\n",
    "        self.arr[p].r = r\n",
    "        if l < r:\n",
    "            mid = (l+r)>>1\n",
    "            self.build(l, mid, 2*p, nums)\n",
    "            self.build(mid+1, r, 2*p+1, nums)\n",
    "            self.arr[p].val = self.arr[2*p].val + self.arr[2*p+1].val\n",
    "        if l == r:\n",
    "            self.arr[p].val = nums[l]\n",
    "        return\n",
    "    \n",
    "    def total(self):\n",
    "        return self.query(0, self.n-1, 1)\n",
    "\n",
    "    def flip(self, p):\n",
    "        self.arr[p].val = (self.arr[p].r - self.arr[p].l + 1) - self.arr[p].val\n",
    "        self.arr[p].modified = not self.arr[p].modified\n",
    "        return\n",
    "\n",
    "    def pushdown(self, p):\n",
    "        if self.arr[p].modified:\n",
    "            self.flip(2*p)\n",
    "            self.flip(2*p+1)\n",
    "            self.arr[p].modified = False\n",
    "        return\n",
    "\n",
    "    def query(self, l, r, p):\n",
    "        # 当前区间是查询区间的子集\n",
    "        if self.arr[p].l >= l and self.arr[p].r <= r:\n",
    "            return self.arr[p].val\n",
    "        # 找到中间点\n",
    "        self.pushdown(p)\n",
    "        m = (self.arr[p].l + self.arr[p].r) >> 1\n",
    "        res = 0\n",
    "        # 递归查询子节点\n",
    "        if l <= m:\n",
    "            res += self.query(l, r, 2*p)\n",
    "        if r > m:\n",
    "            res += self.query(l, r, 2*p+1)\n",
    "        return res\n",
    "    \n",
    "    def modify(self, l, r, p):\n",
    "        # 当前区间是查询区间的子集\n",
    "        if self.arr[p].l >= l and self.arr[p].r <= r:\n",
    "            self.flip(p)\n",
    "            return\n",
    "        # 找到中间点\n",
    "        self.pushdown(p)\n",
    "        m = (self.arr[p].l + self.arr[p].r) >> 1\n",
    "        \n",
    "        # 递归查询子节点\n",
    "        if l <= m:\n",
    "            self.modify(l, r, 2*p)\n",
    "        if r > m:\n",
    "            self.modify(l, r, 2*p+1)\n",
    "        self.arr[p].val = self.arr[2*p].val + self.arr[2*p+1].val\n",
    "        return\n",
    "\n",
    "class SegNode:\n",
    "    def __init__(self):\n",
    "        self.l, self.r = 0, 0\n",
    "        self.val = 0\n",
    "        self.modified = False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ret = []\n",
    "        sum2 = sum(nums2)\n",
    "        tree = SegTree(nums1)\n",
    "        for x0, x1, x2 in queries:\n",
    "            if x0==1:\n",
    "                tree.modify(0, x1, x2)\n",
    "            elif x0==2:\n",
    "                sum2 += tree.arr[0].sum*x1\n",
    "            else:\n",
    "                ret.append(sum2)\n",
    "\n",
    "        return ret\n",
    "\n",
    "class SegNode:\n",
    "    def __init__(self):\n",
    "        self.l = 0\n",
    "        self.r = 0\n",
    "        self.sum = 0\n",
    "        self.lazy = False\n",
    "\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self, nums1):\n",
    "        # 初始化数组\n",
    "        self.arr = [SegNode() for _ in range(4*len(nums1))]\n",
    "        # 开始id，左边界，右边界\n",
    "        self.build(0, 0, len(nums1)-1, nums1)\n",
    "\n",
    "    def build(self, i, l, r, nums1):\n",
    "\n",
    "        # NOTE1 这个很重要，非常非常重要\n",
    "        self.arr[i].l = l\n",
    "        self.arr[i].r = r\n",
    "\n",
    "        if l==r:\n",
    "            self.arr[i].sum = nums1[l]\n",
    "            return\n",
    "\n",
    "        mid = l + ((r-l)>>1)\n",
    "\n",
    "        self.build(2*i+1, l, mid, nums1)\n",
    "        self.build(2*i+2, mid+1, r, nums1)\n",
    "\n",
    "        self.arr[i].sum = self.arr[2*i+1].sum + self.arr[2*i+2].sum\n",
    "\n",
    "    def push_down(self, i):\n",
    "        if self.arr[i].lazy:\n",
    "            \n",
    "            self.arr[2*i+1].lazy = not self.arr[2*i+1].lazy\n",
    "            self.arr[2*i+1].sum = self.arr[2*i+1].r-self.arr[2*i+1].l+1-self.arr[2*i+1].sum\n",
    "\n",
    "            self.arr[2*i+2].lazy = not self.arr[2*i+2].lazy\n",
    "            self.arr[2*i+2].sum = self.arr[2*i+2].r-self.arr[2*i+2].l+1-self.arr[2*i+2].sum  # NOTE2 这里下标写错了，写成2*i+1\n",
    "\n",
    "            self.arr[i].lazy = False\n",
    "\n",
    "    def modify(self, i, l, r):\n",
    "        if self.arr[i].l >= l and self.arr[i].r <= r:\n",
    "            # 当前区间完全被待修改区间包含\n",
    "            self.arr[i].sum = self.arr[i].r-self.arr[i].l+1-self.arr[i].sum\n",
    "            self.arr[i].lazy = not self.arr[i].lazy\n",
    "            return\n",
    "        \n",
    "        self.push_down(i)\n",
    "        \n",
    "        # 最开始是这样写的self.arr[i].l>=l\n",
    "        # print(i, 2*i+1,self.arr[2*i+1].r,l, self.arr[2*i+2].l,r)\n",
    "        if self.arr[2*i+1].r>=l:\n",
    "            self.modify(2*i+1, l, r)\n",
    "        if self.arr[2*i+2].l<=r:\n",
    "            self.modify(2*i+2, l, r)\n",
    "    \n",
    "        self.arr[i].sum = self.arr[2*i+1].sum+self.arr[2*i+2].sum\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.l = self.r = 0\n",
    "        self.s = self.lazy = 0\n",
    "\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, nums):\n",
    "        self.nums = nums\n",
    "        n = len(nums)\n",
    "        self.tr = [Node() for _ in range(n << 2)]\n",
    "        self.build(1, 1, n)\n",
    "\n",
    "    def build(self, u, l, r):\n",
    "        self.tr[u].l, self.tr[u].r = l, r\n",
    "        if l == r:\n",
    "            self.tr[u].s = self.nums[l - 1]\n",
    "            return\n",
    "        mid = (l + r) >> 1\n",
    "        self.build(u << 1, l, mid)\n",
    "        self.build(u << 1 | 1, mid + 1, r)\n",
    "        self.pushup(u)\n",
    "\n",
    "    def modify(self, u, l, r):\n",
    "        if self.tr[u].l >= l and self.tr[u].r <= r:\n",
    "            self.tr[u].lazy ^= 1\n",
    "            self.tr[u].s = self.tr[u].r - self.tr[u].l + 1 - self.tr[u].s\n",
    "            return\n",
    "        self.pushdown(u)\n",
    "        mid = (self.tr[u].l + self.tr[u].r) >> 1\n",
    "        if l <= mid:\n",
    "            self.modify(u << 1, l, r)\n",
    "        if r > mid:\n",
    "            self.modify(u << 1 | 1, l, r)\n",
    "        self.pushup(u)\n",
    "\n",
    "    def query(self, u, l, r):\n",
    "        if self.tr[u].l >= l and self.tr[u].r <= r:\n",
    "            return self.tr[u].s\n",
    "        self.pushdown(u)\n",
    "        mid = (self.tr[u].l + self.tr[u].r) >> 1\n",
    "        res = 0\n",
    "        if l <= mid:\n",
    "            res += self.query(u << 1, l, r)\n",
    "        if r > mid:\n",
    "            res += self.query(u << 1 | 1, l, r)\n",
    "        return res\n",
    "\n",
    "    def pushup(self, u):\n",
    "        self.tr[u].s = self.tr[u << 1].s + self.tr[u << 1 | 1].s\n",
    "\n",
    "    def pushdown(self, u):\n",
    "        if self.tr[u].lazy:\n",
    "            mid = (self.tr[u].l + self.tr[u].r) >> 1\n",
    "            self.tr[u << 1].s = mid - self.tr[u].l + 1 - self.tr[u << 1].s\n",
    "            self.tr[u << 1].lazy ^= 1\n",
    "            self.tr[u << 1 | 1].s = self.tr[u].r - mid - self.tr[u << 1 | 1].s\n",
    "            self.tr[u << 1 | 1].lazy ^= 1\n",
    "            self.tr[u].lazy ^= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(\n",
    "        self, nums1: List[int], nums2: List[int], queries: List[List[int]]\n",
    "    ) -> List[int]:\n",
    "        tree = SegmentTree(nums1)\n",
    "        s = sum(nums2)\n",
    "        ans = []\n",
    "        for op, a, b in queries:\n",
    "            if op == 1:\n",
    "                tree.modify(1, a + 1, b + 1)\n",
    "            elif op == 2:\n",
    "                s += a * tree.query(1, 1, len(nums1))\n",
    "            else:\n",
    "                ans.append(s)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        m = len(queries)\n",
    "        seg_tree = SegTree(nums1)\n",
    "\n",
    "        total = sum(nums2)\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            if queries[i][0] == 1:\n",
    "                l = queries[i][1]\n",
    "                r = queries[i][2]\n",
    "                seg_tree.reverse_range(l, r)\n",
    "            elif queries[i][0] == 2:\n",
    "                total += seg_tree.sum_range(0, n - 1) * queries[i][1]\n",
    "            elif queries[i][0] == 3:\n",
    "                ans.append(total)\n",
    "        return ans\n",
    "\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self, nums):\n",
    "        n = len(nums)\n",
    "        self.arr = [SegNode() for _ in range(n * 4 + 1)]\n",
    "        self.build(1, 0, n - 1, nums)\n",
    "\n",
    "    def sum_range(self, left, right):\n",
    "        return self.query(1, left, right)\n",
    "\n",
    "    def reverse_range(self, left, right):\n",
    "        self.modify(1, left, right)\n",
    "\n",
    "    def build(self, id, l, r, nums):\n",
    "        arr = self.arr\n",
    "        arr[id] = SegNode()\n",
    "        arr[id].l = l\n",
    "        arr[id].r = r\n",
    "        arr[id].lazytag = False\n",
    "        if l == r:\n",
    "            arr[id].sum = nums[l]\n",
    "            return\n",
    "        mid = (l + r) >> 1\n",
    "        self.build(2 * id, l, mid, nums)\n",
    "        self.build(2 * id + 1, mid + 1, r, nums)\n",
    "        arr[id].sum = arr[2 * id].sum + arr[2 * id + 1].sum\n",
    "\n",
    "    # pushdown函数：下传懒标记，即将当前区间的修改情况下传到其左右孩子结点\n",
    "    def pushdown(self, x):\n",
    "        arr = self.arr\n",
    "        if arr[x].lazytag:\n",
    "            arr[2 * x].lazytag = not arr[2 * x].lazytag\n",
    "            arr[2 * x].sum = arr[2 * x].r - arr[2 * x].l + 1 - arr[2 * x].sum\n",
    "            arr[2 * x + 1].lazytag = not arr[2 * x + 1].lazytag\n",
    "            arr[2 * x + 1].sum = arr[2 * x + 1].r - arr[2 * x + 1].l + 1 - arr[2 * x + 1].sum\n",
    "            arr[x].lazytag = False\n",
    "    # 区间修改\n",
    "    def modify(self, id, l, r):\n",
    "        arr = self.arr\n",
    "        if arr[id].l >= l and arr[id].r <= r:\n",
    "            arr[id].sum = (arr[id].r - arr[id].l + 1) - arr[id].sum\n",
    "            arr[id].lazytag = not arr[id].lazytag\n",
    "            return\n",
    "        self.pushdown(id)\n",
    "        mid = (arr[id].l + arr[id].r) >> 1\n",
    "        if arr[2 * id].r >= l:\n",
    "            self.modify(2 * id, l, r)\n",
    "        if arr[2 * id + 1].l <= r:\n",
    "            self.modify(2 * id + 1, l, r)\n",
    "        arr[id].sum = arr[2 * id].sum + arr[2 * id + 1].sum\n",
    "\n",
    "    # 区间查询\n",
    "    def query(self, id, l, r):\n",
    "        arr = self.arr\n",
    "        if arr[id].l >= l and arr[id].r <= r:\n",
    "            return arr[id].sum\n",
    "        if arr[id].r < l or arr[id].l > r:\n",
    "            return 0\n",
    "        self.pushdown(id)\n",
    "        mid = (arr[id].l + arr[id].r) >> 1\n",
    "        res = 0\n",
    "        if arr[2 * id].r >= l:\n",
    "            res += self.query(2 * id, l, r)\n",
    "        if arr[2 * id + 1].l <= r:\n",
    "            res += self.query(2 * id + 1, l, r)\n",
    "        return res\n",
    "\n",
    "class SegNode:\n",
    "    def __init__(self):\n",
    "        self.l = 0\n",
    "        self.r = 0\n",
    "        self.sum = 0\n",
    "        self.lazytag = False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.l = self.r = 0\n",
    "        self.s = self.lazy = 0\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, nums):\n",
    "        self.nums = nums\n",
    "        n = len(nums)\n",
    "        self.tr = [Node() for _ in range(n << 2)]\n",
    "        self.build(1, 1, n)\n",
    "\n",
    "    def build(self, u, l, r):\n",
    "        self.tr[u].l, self.tr[u].r = l, r\n",
    "        if l == r:\n",
    "            self.tr[u].s = self.nums[l - 1]\n",
    "            return\n",
    "        mid = (l + r) >> 1\n",
    "        self.build(u << 1, l, mid)\n",
    "        self.build(u << 1 | 1, mid + 1, r)\n",
    "        self.pushup(u)\n",
    "\n",
    "    def modify(self, u, l, r):\n",
    "        if self.tr[u].l >= l and self.tr[u].r <= r:\n",
    "            self.tr[u].lazy ^= 1\n",
    "            self.tr[u].s = self.tr[u].r - self.tr[u].l + 1 - self.tr[u].s\n",
    "            return\n",
    "        self.pushdown(u)\n",
    "        mid = (self.tr[u].l + self.tr[u].r) >> 1\n",
    "        if l <= mid:\n",
    "            self.modify(u << 1, l, r)\n",
    "        if r > mid:\n",
    "            self.modify(u << 1 | 1, l, r)\n",
    "        self.pushup(u)\n",
    "\n",
    "    def query(self, u, l, r):\n",
    "        if self.tr[u].l >= l and self.tr[u].r <= r:\n",
    "            return self.tr[u].s\n",
    "        self.pushdown(u)\n",
    "        mid = (self.tr[u].l + self.tr[u].r) >> 1\n",
    "        res = 0\n",
    "        if l <= mid:\n",
    "            res += self.query(u << 1, l, r)\n",
    "        if r > mid:\n",
    "            res += self.query(u << 1 | 1, l, r)\n",
    "        return res\n",
    "\n",
    "    def pushup(self, u):\n",
    "        self.tr[u].s = self.tr[u << 1].s + self.tr[u << 1 | 1].s\n",
    "\n",
    "    def pushdown(self, u):\n",
    "        if self.tr[u].lazy:\n",
    "            mid = (self.tr[u].l + self.tr[u].r) >> 1\n",
    "            self.tr[u << 1].s = mid - self.tr[u].l + 1 - self.tr[u << 1].s\n",
    "            self.tr[u << 1].lazy ^= 1\n",
    "            self.tr[u << 1 | 1].s = self.tr[u].r - mid - self.tr[u << 1 | 1].s\n",
    "            self.tr[u << 1 | 1].lazy ^= 1\n",
    "            self.tr[u].lazy ^= 1\n",
    "\n",
    "class Solution:\n",
    "    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        tree = SegmentTree(nums1)\n",
    "        s = sum(nums2)\n",
    "        ans = []\n",
    "        for op, a, b in queries:\n",
    "            if op == 1:\n",
    "                tree.modify(1, a + 1, b + 1)\n",
    "            elif op == 2:\n",
    "                s += a * tree.query(1, 1, len(nums1))\n",
    "            else:\n",
    "                ans.append(s)\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
